The Shape of Edge Differential Privacy

In this work, we consider a randomized-response mechanism called the edgeFlip, which releases a sanitized graph satisfying $\epsilon$-differential privacy. We show that for Random Dot Product Graphs (RDPGs), which are have emerged as a powerful paradigm for statistical analysis of graphs, the output of edgeFlip is also a RDPG. Then, using tools from the burgeoning area of Topological Data Analysis (TDA), we show that when the structure underlying a RDPG in the latent space is supported on a lower-dimensional manifold $\mathcal{M}$, then the $\epsilon$-edge DP synthetic graph obtained via edgeFlip is supported on a manifold $\mathcal M'$ with identical topological features. Additionally, for the privacy budget $\epsilon = 0$, the manifold $\mathcal M'$ retracts to a single point, making the RDPG equivalent to an Erdős-Rényi graph. In essence, for $\epsilon > 0$, the privacy mechanism warps the original manifold $\mathcal M$ in a way such that the subtle topological features are still preserved. Furthermore, we assess the quality of the spectral embedding of the RDPG using persistence diagrams. Asymptotically, we can show that even though the limiting persitence diagram obtained via edgeFlip is different from that of the original graph, the shift-invariant bottleneck distance (a variant of the bottleneck distance which identifies the same input metric space measured in two different units) between the two limiting persitence diagrams converges to zero. We illustrate the advantages of employing edgeFlip in comparison to other alternatives. Lastly, we highlight the benefit of the topological perspective by employing ToMaTO---a topologically-motivated clustering algorithm ---as an alternative to the k-Means algorithm for spectral clustering. To the best of our knowledge, our work is the first to examine the structure of a differential-privacy mechanism through the lens of algebraic topology and statistical inference.