Graph Structure Learning with Privacy Guarantees for Open Graph Data

• URL: http://arxiv.org/abs/2507.19116v1
• Date: Fri, 25 Jul 2025 09:51:12 GMT
• Title: Graph Structure Learning with Privacy Guarantees for Open Graph Data
• Authors: Muhao Guo, Jiaqi Wu, Yang Weng, Yizheng Liao, Shengzhe Chen,
• Abstract summary: We propose a novel privacy-preserving estimation framework for open graph graphs leveraging Gaussian DP (GDP) with a structured noise-injection mechanism.<n>We provide theoretical guarantees on estimation accuracy and extend our method to discrete-variable privacy training.<n> Experimental results in graph learning demonstrate robust performance, offering a viable solution for privacy-preserving graph analysis.
• Score: 6.011824091708078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ensuring privacy in large-scale open datasets is increasingly challenging under regulations such as the General Data Protection Regulation (GDPR). While differential privacy (DP) provides strong theoretical guarantees, it primarily focuses on noise injection during model training, neglecting privacy preservation at the data publishing stage. Existing privacy-preserving data publishing (PPDP) approaches struggle to balance privacy and utility, particularly when data publishers and users are distinct entities. To address this gap, we focus on the graph recovery problem and propose a novel privacy-preserving estimation framework for open graph data, leveraging Gaussian DP (GDP) with a structured noise-injection mechanism. Unlike traditional methods that perturb gradients or model updates, our approach ensures unbiased graph structure recovery while enforcing DP at the data publishing stage. Moreover, we provide theoretical guarantees on estimation accuracy and extend our method to discrete-variable graphs, a setting often overlooked in DP research. Experimental results in graph learning demonstrate robust performance, offering a viable solution for privacy-conscious graph analysis.

Related papers

• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• Unveiling Privacy Vulnerabilities: Investigating the Role of Structure in Graph Data [17.11821761700748]
  This study advances the understanding and protection against privacy risks emanating from network structure. We develop a novel graph private attribute inference attack, which acts as a pivotal tool for evaluating the potential for privacy leakage through network structures. Our attack model poses a significant threat to user privacy, and our graph data publishing method successfully achieves the optimal privacy-utility trade-off.
  arXiv  Detail & Related papers  (2024-07-26T07:40:54Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Privacy-Preserving Graph Embedding based on Local Differential Privacy [26.164722283887333]
  We introduce a novel privacy-preserving graph embedding framework, named PrivGE, to protect node data privacy. Specifically, we propose an LDP mechanism to obfuscate node data and utilize personalized PageRank as the proximity measure to learn node representations. Experiments on several real-world graph datasets demonstrate that PrivGE achieves an optimal balance between privacy and utility.
  arXiv  Detail & Related papers  (2023-10-17T08:06:08Z)
• 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)
• Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach [17.000441871334683]
  We propose a learning framework that can provide node privacy at the user level, while incurring low utility loss. We focus on a decentralized notion of Differential Privacy, namely Local Differential Privacy. We develop reconstruction methods to approximate features and labels from perturbed data.
  arXiv  Detail & Related papers  (2023-09-15T17:35:51Z)
• 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)
• Graph Learning Across Data Silos [10.448384704100684]
  We consider the problem of inferring graph topology from smooth graph signals in a novel but practical scenario.<n>Data are located in distributed clients and prohibited from leaving local clients due to factors such as privacy concerns.<n>We propose an auto-weighted multiple graph learning model to jointly learn a personalized graph for each local client and a single consensus graph for all clients.
  arXiv  Detail & Related papers  (2023-01-17T02:14:57Z)
• DP2-Pub: Differentially Private High-Dimensional Data Publication with Invariant Post Randomization [58.155151571362914]
  We propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases. splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable privacy budget. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy.
  arXiv  Detail & Related papers  (2022-08-24T17:52:43Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Secure Deep Graph Generation with Link Differential Privacy [32.671503863933616]
  We leverage the differential privacy (DP) framework to formulate and enforce rigorous privacy constraints on deep graph generation models. In particular, we enforce edge-DP by injecting proper noise to the gradients of a link reconstruction-based graph generation model. Our proposed DPGGAN model is able to generate graphs with effectively preserved global structure and rigorously protected individual link privacy.
  arXiv  Detail & Related papers  (2020-05-01T15:49:17Z)

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.