Graph data—such as social networks, financial transactions, and knowledge graphs—contains immense utility for downstream machine learning and statistical analysis. However, directly sharing these graphs poses severe privacy risks, potentially exposing sensitive individual relationships or node attributes. To resolve this tension, researchers have converged on a powerful paradigm: differentially private synthetic graph generation. Instead of releasing the original graph or answering individual queries ad-hoc, the goal is to generate a completely new, synthetic graph that acts as a structurally faithful proxy while satisfying formal differential privacy (DP) guarantees.
The Post-Processing Foundation
Why is generating a synthetic graph such an elegant solution for privacy-preserving data sharing? The answer lies in a fundamental mathematical property of differential privacy: immunity to post-processing. As Iftikhar et al. demonstrate in dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees, once a graph's underlying structural distributions or parameters are privatized via noise injection, any subsequent operation performed on those parameters cannot leak additional privacy.
By leveraging this property, data stewards can use a private generative model to output a synthetic adjacency matrix. Once this synthetic graph is released, downstream users can run arbitrary, non-private optimization and machine learning algorithms without consuming any additional privacy budget. For instance, standard clustering algorithms can be applied directly to the sanitized data, as shown by Bun et al. in Differentially Private Correlation Clustering and Imola et al. in Differentially Private Hierarchical Clustering with Provable Approximation Guarantees. Similarly, Graph Neural Networks (GNNs) can be trained safely to defend against topology inference attacks, a strategy explored by Fu et al. in Safeguarding Graph Neural Networks against Topology Inference Attacks and Tran et al. in Heterogeneous Randomized Response for Differential Privacy in Graph Neural Networks.
Bypassing the Noise Penalty via Low-Sensitivity Modeling
The core challenge in differential privacy is the trade-off between sensitivity and utility. Sensitivity measures how much a single element (such as adding or removing an edge or a node) can change the calculated graph statistics. High-dimensional graph representations typically suffer from high sensitivity, meaning that a massive amount of noise must be injected to guarantee privacy, which ultimately destroys the graph's utility, as noted by Goldberg et al. in Benchmarking Fraud Detectors on Private Graph Data.
To circumvent this "noise penalty," effective graph synthesis frameworks decompose the global graph structure into low-dimensional, low-sensitivity components. As systematized by Hu et al. in SoK: Privacy-Preserving Data Synthesis and theoretically validated by Li et al. in Statistical Theory of Differentially Private Marginal-based Data Synthesis Algorithms, high-dimensional data distributions can be accurately approximated by decomposing them into low-dimensional marginals using graphical models like Bayesian networks. By adding noise only to these low-dimensional marginals, the exponential error scaling relative to dimensionality is reduced to polynomial scaling.
In the context of networks, this principle manifests as modeling localized or hierarchical structures:
- Hierarchical Distributions: In Structural-Based Graph Publishing Under Differential Privacy, Liao et al. combine community detection with hierarchical DP to sample edges from noisy hierarchical probability distributions, preserving macro-level statistical features like degree distributions and clustering coefficients.
- Independent Property Partitioning: In Publishing Attributed Social Graphs with Formal Privacy Guarantees, Jorgensen et al. partition the total privacy budget to independently estimate distinct, low-sensitivity properties—such as node attribute distributions and structural topology—before recombining them in a post-processing pipeline to preserve homophily.
Preserving Global Topology and Higher-Order Structures
A synthetic graph is only valuable if its macro-level topology mirrors the original network. A key mechanism for achieving this is private cut sparsification. Here, the synthetic graph is generated to preserve the weights of all possible cuts within a specific error margin under differential privacy, ensuring that global connectivity and community boundaries remain intact (Bun et al.; Imola et al.).
However, simple edge cuts often fail to capture complex, higher-order clustering behavior like triangles. To address the mathematical non-linearity of these structures, Peng et al. frame graph synthesis as an optimization problem using stochastic mirror descent in Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts. By iteratively updating synthetic edge weights based on noisy gradients of target metrics, they successfully align the synthetic graph with the original's triangle-motif cuts.
When the privacy goal shifts to the more stringent standard of node-level differential privacy (protecting an entire node and all its connected edges), the sensitivity spikes dramatically. To counter this, the authors of Community Preserved Social Graph Publishing with Node Differential Privacy extract global features using a private version of Oja's algorithm and reconstruct the synthetic graph via regularized Laplacian estimation. This allows the synthetic network to maintain essential community properties even under strict node-level privacy constraints.
Key Foundational Work
Iterative Constructions and Private Data Release (2012) — contributed 3 concept elements to this direction.
Publishing Attributed Social Graphs with Formal Privacy Guarantees (2016) — contributed 2 concept elements to this direction.