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 a network representation as well as a 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 graphs which is $\epsilon$-differentially private at the vertex level, while preserving utility. We provide theoretical guarantees for the accuracy of the private synthetic graphs using an extension of the Wasserstein metric to structured data, namely the fused Gromov-Wasserstein distance.