Empirical Auditing of Edge-Private Graph Generators

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 mechanism- and network-dependent, with learned representations revealing information not captured by conventional local statistics.