mlsanityData to 14 Oct 2026

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

arXiv 2504.17274 ↗First posted 24 Apr 2025cs.LG math.ST stat.MLcited by 0

Not on the map. Why?

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.

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

28 of 78 references.

References · 28

  1. 2018UMAP: Uniform Manifold Approximation and Projection for Dimension Reductioncited by 2,898
  2. 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
  3. 2014DeepWalk: Online Learning of Social Representationscited by 1,547
  4. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  5. 2017Community Detection and Stochastic Block Modelscited by 319
  6. 2017An introduction to Topological Data Analysis: fundamental and practical aspects for data scientistscited by 172
  7. 2013Consistency of spectral clustering in stochastic block modelscited by 129
  8. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 107
  9. 2017Statistical inference on random dot product graphs: a surveycited by 70
  10. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  11. 2016Community Detection in Degree-Corrected Block Modelscited by 36
  12. 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 33
16 more
  1. 2015Minimax Rates of Community Detection in Stochastic Block Modelscited by 25
  2. 2013Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embeddingcited by 23
  3. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  4. 2020Locally Differentially Private Analysis of Graph Statisticscited by 20
  5. 2020Manifold structure in graph embeddingscited by 17
  6. 2021Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergencecited by 17
  7. 2021Private Graph Data Release: A Surveycited by 15
  8. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  9. 2020On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Modelscited by 6
  10. 2021Consistent Spectral Clustering of Network Block Models under Local Differential Privacycited by 6
  11. 2022Network change point localisation under local differential privacycited by 5
  12. 2015Sharing Social Network Data: Differentially Private Estimation of Exponential-Family Random Graph Modelscited by 4
  13. 2023Triangle Counting with Local Edge Differential Privacycited by 4
  14. 2024Differentially private exact recovery for stochastic block modelscited by 4
  15. 2024PriME: Privacy-aware Membership profile Estimation in networkscited by 4
  16. 2024A Differentially Private Clustering Algorithm for Well-Clustered Graphscited by 2

Built on by

Not cited yet.