An Empirical Audit of Privacy Leakage in Edge-Private Graph Generators

The researchers conduct an empirical audit of edge-private graph generators, using a statistically verifiable lower bound on privacy loss to test whether the outputs of edge-adjacency inputs remain distinguishable. Their framework centers on the geometric structure of target edges and compares direct-edge, local-structure, and GNN-based attacks. Experiments on two generators and two networks show that privacy leakage varies by mechanism and network, and that learned representations leak information not captured by traditional local statistics.