Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance

Networks are popular representations of complex data. In particular, differentially private synthetic networks are much in demand. Here, instead of starting from a network, we start with the complex data set itself and construct both a network representation and a corresponding synthetic network generator. We build a network model directly based on the underlying complex system data, capturing its structure and attributes. Using a random connection model, we devise an effective algorithmic approach for generating attributed synthetic networks which is $\epsilon$-differentially private at the vertex level, while preserving utility. We provide theoretical guarantees for the accuracy of the private synthetic networks using the fused Gromov-Wasserstein distance.