Signal Recovery from Random Dot-Product Graphs under Local Differential Privacy

Siddharth Vishwanath, Jonathan HehirAISTATS 2025

Abstract

Local Differential Privacy (LDP) provides strong privacy guarantees for graph data by allowing users to obfuscate their own connections. However, this often comes at a significant cost to data utility. This paper addresses the challenge of recovering latent signals from Random Dot-Product Graphs (RDPGs) under LDP. We demonstrate that the standard edgeFlip mechanism induces a predictable geometric distortion in the latent space. By exploiting a novel closure property, we develop a privacy-adjusted spectral embedding technique and utilize topological data analysis to recover hidden structures. Our results show that near-optimal recovery is possible above a specific detection threshold, providing a theoretical and practical framework for private graph analysis.

Introduction

In modern data science, graphs are indispensable for modeling complex relationships in social networks, financial systems, and biological structures. However, the sensitivity of edge information necessitates robust privacy protections. Differential Privacy (DP) has emerged as the gold standard, with Local Differential Privacy (LDP) offering the strongest protection by removing the need for a trusted central curator. Despite its benefits, LDP introduces substantial noise, often obscuring the very signals researchers aim to extract.

A recent study presented at AISTATS 2025 by Siddharth Vishwanath and Jonathan Hehir tackles this utility gap. They focus on Random Dot-Product Graphs (RDPGs), where node connections are governed by latent positions in a low-dimensional space. The core question is whether the original "signal"—the latent positions and topological features—can be recovered after every user has independently flipped their edge statuses to satisfy privacy requirements.

The Geometry of Privacy: The Closure Property

The researchers' primary theoretical contribution is the discovery of a Closure Property for privatized RDPGs. They prove that applying the edgeFlip mechanism to a Generalized RDPG results in a new graph that remains a Generalized RDPG, albeit in a higher dimension ($d+1$).

This finding allows the impact of privacy to be viewed as a specific geometric transformation. Specifically, the privacy mechanism "squeezes" the latent positions toward a central point in the embedding space. Because this distortion is mathematically well-defined and depends predictably on the privacy budget ($\epsilon$), it can be systematically reversed.

Geometric distortion of latent positions under varying privacy budgets ($\epsilon$).

Methodology: Privacy-Adjusted Spectral Embedding

Building on the closure property, the authors propose Algorithm 1: Privacy-Adjusted Spectral Embedding. This method involves modifying the observed adjacency matrix based on the known privacy budget $\epsilon$ to account for the expected noise, followed by spectral decomposition to project the nodes into a latent space.

In addition to coordinate recovery, the paper employs Topological Data Analysis (TDA). Since the privacy transformation is a homeomorphism (a continuous deformation), it preserves fundamental topological features like clusters and loops. By using persistence diagrams, the authors can identify structural motifs that traditional clustering algorithms might fail to detect under high noise.

Results and Phase Transitions

The effectiveness of the proposed estimator was validated through both synthetic and real-world datasets, including Stochastic Block Models (SBMs) and the OpenFlights dataset. A key finding is the existence of a phase transition or detection threshold.

The authors derive minimax lower bounds showing that consistent recovery is only possible when the graph is sufficiently dense relative to the privacy noise. Specifically, the sparsity parameter $\rho$ effectively becomes $\rho^2$ in the private setting, highlighting a "sparsity penalty" inherent to LDP.

Phase transition in signal recovery as a function of graph size ($n$) and privacy budget ($\epsilon$).

Empirically, the privacy-adjusted estimator achieves error rates that match these theoretical bounds within a logarithmic factor. In complex scenarios, such as recovering disjoint circular clusters, the TDA-based approach significantly outperformed standard methods like k-means and DBSCAN, demonstrating the robustness of topological features against local noise.

Conclusion

This work provides a rigorous foundation for analyzing graphs under local privacy constraints. By reframing privacy as a geometric distortion rather than mere information loss, the authors show that significant utility can be preserved. While the current framework requires relatively dense graphs, it paves the way for future research into sparse network recovery and the application of these techniques to broader classes of latent position models.

Summary updated

BibTeX
@inproceedings{vishwanath2025signal,
  author = {Siddharth Vishwanath and Jonathan Hehir},
  title = {{Signal Recovery from Random Dot-Product Graphs under Local Differential Privacy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}

Loading related content...

Figure