# Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy

arXiv: https://arxiv.org/abs/2504.17274 · HTML: https://mlsanity.com/paper/2504.17274/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 78 references that are in the map.
- First posted on arXiv 24 Apr 2025.

## Builds on (most cited first, 28 of 28)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists](https://mlsanity.com/paper/1710.04019/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Manifold structure in graph embeddings](https://mlsanity.com/paper/2006.05168/) (2020)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Private Graph Data Release: A Survey](https://mlsanity.com/paper/2107.04245/) (2021)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models](https://mlsanity.com/paper/2003.14250/) (2020)
- [Consistent Spectral Clustering of Network Block Models under Local Differential Privacy](https://mlsanity.com/paper/2105.12615/) (2021)
- [Network change point localisation under local differential privacy](https://mlsanity.com/paper/2205.07144/) (2022)
- [Sharing Social Network Data: Differentially Private Estimation of Exponential-Family Random Graph Models](https://mlsanity.com/paper/1511.02930/) (2015)
- [Triangle Counting with Local Edge Differential Privacy](https://mlsanity.com/paper/2305.02263/) (2023)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [PriME: Privacy-aware Membership profile Estimation in networks](https://mlsanity.com/paper/2406.02794/) (2024)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)

## Abstract (arXiv)

We consider the problem of recovering latent information from graphs under varepsilon-edge local differential privacy where the presence of relationships/edges between two users/vertices remains confidential, even from the data curator. For the class of generalized random dot-product graphs, we show that a standard local differential privacy mechanism induces a specific geometric distortion in the latent positions. Leveraging this insight, we show that consistent recovery of the latent positions is achievable by appropriately adjusting the statistical inference procedure for the privatized graph. Furthermore, we prove that our procedure is nearly minimax-optimal under local edge differential privacy constraints. Lastly, we show that this framework allows for consistent recovery of geometric and topological information underlying the latent positions, as encoded in their persistence diagrams. Our results extend previous work from the private community detection literature to a substantially richer class of models and inferential tasks.