Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
This addresses the need for private synthetic networks for method and algorithm development, offering a solution with privacy and utility guarantees, though it builds on existing work and is incremental in nature.
The paper tackles the problem of generating differentially private synthetic graphs from complex data, developing a method that is ε-differentially private at the vertex level and preserves utility under a new fused Gromov-Wasserstein distance, with theoretical guarantees for accuracy.
Networks are popular for representing complex data. In particular, differentially private synthetic networks are much in demand for method and algorithm development. The network generator should be easy to implement and should come with theoretical guarantees. Here we start with complex data as input and jointly provide a network representation as well as a synthetic network generator. Using a random connection model, we devise an effective algorithmic approach for generating attributed synthetic graphs which is $ε$-differentially private at the vertex level, while preserving utility under an appropriate notion of distance which we develop. We provide theoretical guarantees for the accuracy of the private synthetic graphs using the fused Gromov-Wasserstein distance, which extends the Wasserstein metric to structured data. Our method draws inspiration from the PSMM method of \citet{he2023}.