[2507.19116] Graph Structure Learning with Privacy Guarantees for Open Graph Data

Computer Science > Machine Learning arXiv:2507.19116 (cs) [Submitted on 25 Jul 2025 (v1), last revised 21 Mar 2026 (this version, v2)] Title:Graph Structure Learning with Privacy Guarantees for Open Graph Data Authors:Muhao Guo, Jiaqi Wu, Yang Weng, Yizheng Liao, Shengzhe Chen View a PDF of the paper titled Graph Structure Learning with Privacy Guarantees for Open Graph Data, by Muhao Guo and 4 other authors View PDF HTML (experimental) 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 i...