It is often desirable to generate and release synthetic graphs, which resemble real-world data, in a privacy-preserving way. While substantial progress has been made in designing private graph synthesizers (PGS), opportunities remain for more explicit connections between synthesizer models and privacy evaluation, and better accounting for output variation. This paper proposes GSynPEF, a practical framework for empirical evaluation of privacy and utility in settings for which a real-world graph is given as input and output synthetic graph(s) are observed. Our framework links a broad class of graph synthesizers (both statistical and deep-learning based) with privacy metrics, expanding evaluation dimensions to practical utility and risk, through empirical analysis of multiple actual outputs. The framework accommodates both an Exact Solution scenario, where synthesizer behavior is directly observable, and a Monte Carlo Approximation scenario where only synthetic outputs from a black box synthesizer are available. Extensive experiments on four real-world datasets and seven widely used graph synthesizers demonstrate framework's versatility, enabling privacy evaluation for different attack goals (e.g., to infer an edge or node) and capabilities (e.g., observing one or multiple synthetic graphs). We analyze evaluation results by examining the relationship between graph statistics and synthesizer design choices, providing insights for data curators in PGS selection and researchers for improved PGS design.
Figures & tables
Figure 1: Conceptual Diagram. Input of graph synthesizer ( M ) is original graph ( G ), and output is synthetic graph ( o ) intended as a proxy generated for G . Proposed framework is able to evaluate a setup ( G×M ) from privacy/utility, with actual outputs of M(G) .
Figure 2: Overview of GSynPEF. Input is a “setup”, which includes a dataset G and a graph synthesizer M . Outputs are evaluation results, from different granularity levels by considering privacy/utility dimensions. GSynPEF incorporates three phases: generation, computation and evaluation. (i) The generation phase involves two parallel steps: generation of graph neighbors and multiple outputs for a given setup. ES scenario models privacy loss to an adversary who has access to edge probability matrix PA , while MCA scenario models privacy loss to an adversary who only gets to see some number of draws from M with the target dataset (Section 3.2 ). (ii) The computation phase describes the process to compute privacy loss and utility error values. Privacy loss is computed as PLRVs over the computation space Z , where each cell corresponds to an output–neighbor pair and collectively forms matrix IPLRV . Utility error is evaluated using both label-dependent and label-independent metrics (Section 3.3 ). (iii) The evaluation phase extracts metrics from computed values with various granularities. Edge/node privacy aligns with different attack goals, and per output/setup privacy corresponds to different attack capabilities (Section 3.4 ).
Notation
Description
M
A randomized mechanism (a graph synthesizer with randomness)
G(V,E)
Original graph with nodes set V and edge set E .
G′
Edge neighbor of original graph
O
Output set of M(G) , with length Itero . O is [o1,o2,...o−1]
A
Adjacency matrix of original graph
N
Node number in G
Table 1: Notations
Figure 3: Evaluation Vector Formation. From computed privacy/utility values to evaluation vector and scatter plot.
Dataset
∣ V ∣
∣ E ∣
Density
Nor. Rank
Karate Club
34
78
0.14
0.71
HIV
40
41
0.05
0.80
CEO
40
95
0.12
0.75
EU-Email
1005
16706
0.03
0.98
Table 2: Dataset Statistics
Figure 4: Sample Size Validation ( Itero ).
Figure 5: Exact Solution vs. Monte Carlo Approximation.
Statistical Graph Synthesizers (SGS)
Deep Graph Synthesizers (DGS)
Within one SGS (SGF, with different α )
Across different SGS
Across different DGS
V\ M
0.1
0.3
0.5
0.7
0.9
CL
BTER
SBM
SGF
GAE
VGAE
ARGA
mo
1.51
2.22
2.15
3.61
4.23
0.32
5.48
5.15
2.15
2.52
0.0
10.98
ϵo
6.67
7.90
7.00
23.03
23.03
1.71
32.24
31.37
7.00
6.86
0.03
21.14
me
2.78
2.35
2.13
2.80
3.25
0.32
4.19
3.62
2.13
2.26
0.0
10.30
ϵe
7.62
6.23
5.67
2.80
3.25
1.95
9.39
8.47
5.67
5.91
0.03
18.40
Table 3: Setup Evaluation Vectors within/across M ( G : Karate Club ×M : Statistical / Deep Graph Synthesizers).
Figure 6: Evaluation per Output across M . (top: average-case privacy, bottom: worst-case privacy; left: label-independent utility, right: label-dependent utility.)
Figure 7: Risk Fraction Heatmap across M . (1st row: RF3 , 2nd row: RF4 )
Figure 8: Edge/Node Privacy Loss across G and M . (left: grouped by G ; right: grouped by M , edge privacy.)
Figure 9: Sampling Results. Column (a) and (b) show the computation convergence in relative error across G and M . Row (c) left shows the convergence of estimated mo ; right shows the relative error changing with graph size N .
Figure 10: Itero Testing.
Statistical Graph Synthesizer
Deep Graph Synthesizer
V\ M
CL
BTER
SBM
SGF
GAE
VGAE
ARGA
mo
0.13(0.13)
24.59(0.08)
47.18(0.06)
33.13(0.03)
0.(0.)
0.01(0.51)
0.33(0.23)
ϵo
0.38(0.05)
49.86(0.07)
99.57(0.05)
50.91(0.03)
0.(0.)
0.05(0.08)
0.80(0.22)
me
0.13(0.09)
25.12(0.07)
47.99(0.05)
32.85(0.02)
0.(0.)
0.(0.52)
0.36(0.22)
ϵe
0.13(0.09)
25.12(0.07)
47.99(0.05)
32.85(0.02)
0.(0.)
0.(0.52)
0.36(0.22)
mn
0.13(0.09)
24.84(0.06)
47.63(0.05)
32.49(0.02)
0.(0.)
0.(0.59)
0.37(0.22)
Table 4: Setup Evaluation Vectors within/across M . ( G : EU-Email ×M : Statistical Graph Synthesizer/ Deep Graph Synthesizer), with average metric and relative uncertainty score.
Synthetic data evaluation measures whether generated examples preserve the properties needed for a stated use, including fidelity, privacy, and utility.
Differentially private (DP) synthetic data enables the use of sensitive datasets while providing strong privacy guarantees. Recently, Private Evolution (PE) has emerged as a promising framework for generating DP synthetic data using only inference APIs of foundation models. However, suitable foundation models are not always available for every private data domain. In this paper, we show that PE is more general than previously understood and can incorporate APIs beyond foundation models. In particular, we show that state-of-the-art non-neural-network data synthesizers, including computer graphics-based image generators and physics simulation tools (which we refer to as simulators), integrate naturally into PE. We call the resulting method Sim-PE. Sim-PE broadens the applicability of PE while improving performance. For image synthesis, Sim-PE improves downstream classification accuracy by up to 3x, reduces FID by up to 80%, and is significantly more efficient. We further show that simulators and foundation models can be seamlessly combined within Sim-PE for additional gains. Beyond performance improvements, Sim-PE enables new DP applications that are difficult or impossible for existing methods, including generating DP control signals whose execution reproduces the distribution of private observations. The code is open-sourced in the Private Evolution Python library: https://github.com/microsoft/DPSDA
Zinan Lin, Tadas Baltrusaitis, Wenyu Wang +1
Microsoft Research Redmond, WA, USA · Microsoft Cambridge, UK · Redmond, WA, USA
Time series forecasting in privacy-sensitive domains often requires training models on released data rather than original observations. Synthetic time series generation has been developed primarily for data augmentation, where generated series supplement the original training set. How well these methods perform when fully replacing the original data - and how much privacy risk the released series carry - remains underexplored. We address this gap through a benchmark evaluating synthetic generation methods and noise-based anonymization baselines under a Train on Synthetic, Test on Real (TSTR) protocol. We jointly assess forecasting performance and distance-based empirical privacy risk across seven datasets, characterizing the trade-off between these objectives. We also introduce Grasynda-P, a privacy-motivated extension of the graph-based generator Grasynda, incorporating matrix ensembling and kernel density estimation. Our results show that: (1) no generation method fully substitutes for original training data; (2) noise-based anonymization yields the strongest privacy but the worst forecasting performance; (3) simple transformation-based generators outperform deep generative models for forecasting in this setting; and (4) Grasynda-P lies on the Pareto frontier, achieving competitive forecasting with stronger privacy separation than other generators. This benchmark establishes a reference point for evaluating and developing new privacy-aware synthetic time series generation methods.
Luis Amorim, Vitor Cerqueira, Moises Santos +2
Faculdade de Engenharia da Universidade do Porto, Porto, Portugal · University of Coimbra, Coimbra, Portugal · Laboratory for Artificial Intelligence and Computer Science (LIACC), Portugal +3
We empirically audit privacy leakage by testing whether outputs from edge-neighbouring inputs remain distinguishable, using statistically valid lower bounds on the privacy loss witnessed by our attacks. Our framework compares direct-edge, local-structural, and GNN-based attacks through the geometry surrounding a target edge. Experiments across two generators and two networks show that privacy leakage is both mechanism- and network-dependent, with learned representations revealing information not captured by conventional local statistics.
Anum Fatima, Stratis Limnios, James Adams +4
Department of Statistics University of Oxford Oxford, United Kingdom · Plenitude Consulting, London, United Kingdom · National Physical Laboratory Teddington, United Kingdom +3