Pith. sign in

REVIEW 3 major objections 4 minor 77 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that edgeFlip, a standard local edge-differential-privacy mechanism, maps generalized random dot-product graphs to the same model class with one extra latent dimension, and that a privacy-adjusted spectral embedding then…

desk verdict A genuinely nice closure result for private GRDPGs, with an upper-bound proof that overstates its density regime and a TDA section that needs more care. read the letter →

arxiv 2504.17274 v1 pith:XIUAE3LE submitted 2025-04-24 cs.LG math.STstat.MLstat.TH

Siddharth Vishwanath , Jonathan Hehir This is my paper · ORCID
classification cs.LGmath.STstat.MLstat.TH MSC 62C2062H1205C80
keywords localdifferentialprivacygeneralizedrandomdot-productgraphsedgeFlipspectralembeddinglatentpositionestimationminimaxratespersistencediagrams
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that a standard local-differential-privacy mechanism for graphs, edgeFlip, does not destroy the latent geometry encoded in the graph; it transforms a generalized random dot-product graph into another such graph with one extra latent dimension. This closure lets a privacy-adjusted spectral embedding recover the original latent positions consistently and nearly optimally in the $\ell_{2,\infty}$ metric, with a matching lower bound up to a $\sqrt{\log n}$ factor. The same convergence rate carries over to persistence diagrams, so topological features such as clusters and loops can be recovered privately. A sympathetic reader should care because most prior private-graph work stopped at community detection in stochastic block models, while this paper extends the argument to a substantially richer nonparametric family.

What carries the argument

The central object is the edgeFlip mechanism together with the geometric closure map $\varphi_\varepsilon$. edgeFlip flips each edge with probability $\pi(\varepsilon)=1/(e^\varepsilon+1)$; writing $\sigma(\varepsilon)=\sqrt{(e^\varepsilon-1)/(e^\varepsilon+1)}$ and $\tau(\varepsilon)=\sqrt{1/(e^\varepsilon+1)}$, the privatized edge probabilities become $\tau(\varepsilon)^2+\sigma(\varepsilon)^2\rho_n X_i^T I_{p,q} X_j$, which are exactly inner products in $\mathbb{R}^{d+1}$ after appending the constant coordinate $\tau(\varepsilon)$ and scaling the original coordinates by $\sigma(\varepsilon)\rho_n^{1/2}$. Algorithm 1 reverses this distortion by forming $\tilde A=\sigma(\varepsilon)^{-2}(M_\varepsilon(A)-\tau(\varepsilon)^2 11^T)$, estimating $\rho_n$ from the average privatized edge, and taking the adjacency spectral embedding. The extra dimension is the geometric footprint of the privacy noise.

What would settle it

Simulate $A\sim G(P,\rho_n;p,q)$ with $n\rho_n=\log^{2.5} n$ (so $n\rho_n=\omega(\log n)$ but $n\rho_n=o(\log^4 n)$), privatize with edgeFlip at a fixed $\varepsilon$, run Algorithm 1, and measure $d_{2,\infty}(\hat X/\sqrt{\hat\rho_n},X)$ across increasing $n$. If the error does not track $O\bigl(\log n/\sqrt{n\sigma(\varepsilon)^4\rho_n^2}\bigr)$ and instead levels off, the spectral-concentration step imported from non-private GRDPG bounds is the failing link in the stated regime.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: if $(A,X)\sim G(P,\rho_n;p,q)$ is a generalized random dot-product graph, then after edgeFlip the privatized graph satisfies $(M_\varepsilon(A),\varphi_\varepsilon(X))\sim G(\varphi_{\varepsilon\#}P,1;p+1,q)$, where $\varphi_\varepsilon(x)=\tau(\varepsilon)\oplus\sigma(\varepsilon)\rho_n^{1/2}x$ appends one constant coordinate and scales the original latent positions. Consequently, Algorithm 1 achieves $d_{2,\infty}(\hat X/\sqrt{\hat\rho_n},X)=O\bigl(\log n/\sqrt{n\sigma(\varepsilon)^4\rho_n^2}\bigr)$ with high probability when $n\rho_n=\omega(\log n)$, while Theorem 3.2 shows that no $\varepsilon$-edgeLDP mechanism can beat $\Omega\bigl(\sqrt{\log n/(n\sigma(\varepsilon)^4\rho_n^2)}\bigr)$ in the regime $\varepsilon<3\rho_n/8$. Theorem 3.4 extends the same rate to the bottleneck distance between persistence diagrams. Together these results say that, up to logarithmic factors, edgeFlip is an optimal privacy mechanism for this problem and the privacy-adjusted spectral embedding is an optimal estimator.

Load-bearing premise

The upper-bound proof assumes that spectral-concentration results proven for ordinary Bernoulli adjacency matrices carry over to the recentered privatized matrix $M_\varepsilon(A)-\tau(\varepsilon)^2 11^T$, including a sparsity regime $n\rho_n=\omega(\log n)$ that may be too sparse for those results; the paper itself notes that its introduction relies on the denser $\omega(\log^4 n)$ regime.

Editorial extensions

If this is right

  • After edgeFlip, the privatized graph is itself a GRDPG with effective sparsity $\sigma(\varepsilon)^2\rho_n$ and one additional latent dimension, so standard GRDPG inference tools can be applied once the $\tau(\varepsilon)^2$ offset is subtracted and the scale is corrected.
  • The minimax lower bound shows that local edge privacy reduces the effective sample size from $n$ to $\sigma(\varepsilon)^4 n$ and amplifies sparsity from $\rho_n$ to $\rho_n^2$; consequently, consistent latent-position recovery is possible only when $\sigma(\varepsilon)^4\rho_n^2=\tilde{\Omega}(1/n)$, which can be read as a phase-transition boundary for private estimation.
  • Algorithm 1's rate matches the non-private minimax rate after replacing $\rho_n$ by $\sigma(\varepsilon)^4\rho_n^2$, up to the same $O(\sqrt{\log n})$ gap that already appears in the best-known non-private GRDPG bounds.
  • Persistence diagrams computed from the privacy-adjusted embedding converge to those of the latent positions at the same rate as the embedding itself, so private recovery of connected components, loops, and other topological features is achieved under $\varepsilon$-edgeLDP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implicit consequence of the closure theorem is that edgeFlip can act as a reusable privacy layer for any downstream estimator that is equivariant under the GRDPG's symmetries and Lipschitz in the $d_{2,\infty}$ metric, not just for spectral and topological methods.
  • The same geometric lens suggests a route to private graphon estimation: for exchangeable latent-position models whose edge probabilities are bilinear in latent features, edgeFlip should correspond to appending a constant spike coordinate, which may turn existing graphon estimators into privacy-adjusted estimators at the cost of the sparsity penalty identified here.
  • A testable extension is to check whether the sparsity amplification $\rho_n\mapsto\rho_n^2$ is forced by local privacy or by edge privacy itself; if central edge DP avoids the amplification, then the local-DP requirement, rather than edge confidentiality per se, is the source of the extra statistical cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies latent-position recovery from generalized random dot-product graphs (GRDPGs) under ε-edge local differential privacy, using the edgeFlip mechanism. The central theoretical contribution is Theorem 3.1, which states that edgeFlip maps a GRDPG with signature (p,q) and sparsity ρ_n to another GRDPG with signature (p+1,q), sparsity 1, and latent positions φε(x) = τ(ε) ⊕ σ(ε)ρ_n^{1/2}x. Building on this closure property, the authors prove a minimax lower bound for latent-position estimation under ε-edgeLDP (Theorem 3.2), propose a privacy-adjusted spectral embedding (Algorithm 1), and claim near-minimax optimal consistency in Theorem 3.3 under nρ_n = ω(log n). They then extend the result to persistence diagrams (Theorem 3.4) and illustrate the methods on synthetic and real-world data.

Significance. If the main theorems hold, the paper is a substantial contribution: it moves private graph inference from stochastic block models to the much richer GRDPG class, gives a clean geometric interpretation of edgeFlip, and provides the first minimax lower bound for latent-position estimation under local edge DP, together with a topological-data-analysis downstream application. The closure argument in Theorem 3.1 is elegant and checkable, and the lower-bound proof via Le Cam's lemma is a credible technical core. The paper also ships reproducible code and experiments with clearly described settings. However, the central upper-bound proof in Theorem 3.3 imports spectral concentration results under conditions that are not verified, and the stated density regime conflicts with the proof's own requirements; these issues must be resolved before the near-minimax optimality claim is established.

major comments (3)
  1. [Section 3.3 / Appendix C.4, Eq. (32)] Theorem 3.3 is stated under nρ_n = ω(log n), but the proof imports Proposition B.1 and the results of [56, Theorem 1] and [2, Theorem 4], whose stated condition is nρ_n = ω(log^4 n). After edgeFlip the relevant sparsity scale of the privatized graph is t_n = σ(ε)^2 ρ_n ≤ ρ_n, so the theorem's assumption does not imply n t_n = ω(log^4 n); for example, with fixed ε and ρ_n = log^{3/2} n / n, we have nρ_n = ω(log n) but n t_n = o(log^4 n). The introduction's last paragraph and Proposition B.1 both state the ω(log^4 n) regime, so either Theorem 3.3's assumption must be strengthened to nσ(ε)^2 ρ_n = ω(log^4 n) or its equivalent, or a new argument must be supplied that works under nρ_n = ω(log n). As written, the consistency range and the near-minimax optimality claim are overstated.
  2. [Appendix C.4, Step 1 and Lemma B.3] The matrix A = Mε(A) − τ(ε)^2 1_n1_n^T is not a Bernoulli GRDPG adjacency matrix, yet the proof applies [41, Theorem 5.2], [56, Lemma 12], and [10, Propositions 6.3 and 6.5] to it. These results are stated for graphs whose entries are independent Bernoulli with expectation P; here A has entries taking values 1−τ² and −τ², with variance (τ²+σ²ρ P_ij)(1−τ²−σ²ρ P_ij), which differs from P_ij(1−P_ij). When τ² is non-negligible, the noise has a dense component that does not vanish with ρ_n. The proof does not verify the effective-sparsity condition n max_ij P_ij = nσ(ε)^2 ρ_n ≫ log^c n needed for the imported spectral bounds, nor the corresponding row-wise eigenvector perturbation assumptions. Since this is the sole route to Eqs. (32)–(35), the high-probability bound in Theorem 3.3 is not established as written.
  3. [Appendix B.1, Lemma B.3, and Appendix C.4] The map φε is defined inconsistently between Theorem 3.1 and the appendix. Theorem 3.1 uses φε(x) = τ(ε) ⊕ σ(ε)ρ_n^{1/2}x, but Appendix B.1 defines φε(x) = τ(ε) ⊕ σ(ε)x, and Lemma B.3 accordingly computes E[Mε(A)_ij] = σ(ε)^2 X_i^T I_{p,q} X_j + τ(ε)^2, omitting the ρ_n factor. Appendix C.4 invokes Lemma B.3 while using the ρ_n-containing form of the expected adjacency P. The proof needs a consistent definition of φε and corrected lemmas, or an explicit statement that the ρ_n-free version is used only for the noise bound and not for the spectral separation step.
minor comments (4)
  1. [Section 3.3, Theorem 3.3] The rate O(log n / √(n σ(ε)^4 ρ_n^2)) can diverge when nσ(ε)^4ρ_n^2 = o(log n), so the theorem should either state explicitly the consistency condition nσ(ε)^4ρ_n^2 = ω(log n) or clarify that consistency is claimed only in that regime.
  2. [Appendix C.5, final displayed equation] The proof of Theorem 3.4 concludes with W∞(D̂_n, D_n) = O(log n / √(σ² n ρ_n)), which does not match the stated rate O(log n / √(n σ⁴ ρ_n²)) in Theorem 3.4; in addition, the quantity T1 is written as ‖qρ_n qX − XQ_n^{-1}‖_{2,∞}, where a missing −1/2 exponent on qρ_n appears likely. Please correct the normalization and reconcile the final rate with the theorem statement.
  3. [Algorithm 1, Step 2] The estimator qρ_n is defined as an average of qA_ij, which can be negative or exceed 1 for finite samples, yet the algorithm's return statement claims qρ_n ∈ [0,1]; specify a clipping or truncation step if one is intended.
  4. [Appendix, Table 1] The notation table entry for ΔX is incomplete, reading 'ΔX = for ξ∼ P'; it should define ΔX = n^{-1}X^TX as in Appendix A.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central results are derived from the edgeFlip transition probabilities and external spectral benchmarks; the lone self-citation is contextual.

full rationale

The paper's central derivation chain is self-contained rather than circular. Theorem 3.1 proves closure of GRDPGs under edgeFlip by direct calculation: for (A,X)~G(P,rho_n;p,q), the conditional edge probability of M_epsilon(A) is pi(epsilon)(1-rho_n X_i^T I_{p,q} X_j)+(1-pi(epsilon))rho_n X_i^T I_{p,q} X_j = tau(epsilon)^2 + sigma(epsilon)^2 rho_n X_i^T I_{p,q} X_j = phi_epsilon(X_i)^T I_{p+1,q} phi_epsilon(X_j), so the privatized graph has the claimed GRDPG distribution with latent positions phi_epsilon(X). This is not an input assumed into the conclusion; it is a consequence of the mechanism definition. The minimax lower bound (Theorem 3.2) is built on Le Cam's lemma and a chi-squared divergence calculation over explicitly constructed latent-position hypotheses; no parameter is fitted and then renamed as a prediction. The upper bound (Theorem 3.3) centers the privatized adjacency matrix and imports spectral perturbation and residual bounds from Rubin-Delanchy et al. [56], Cape et al. [10], and Lei-Rinaldo [41], which are external benchmarks rather than results of the present authors. Whether all technical conditions of those results are verified at the stated sparsity level n rho_n = omega(log n) is a correctness concern, not a circularity: the proof would fail for an external reason, not because the conclusion was assumed. The paper itself notes in the introduction that its upper bounds operate in the denser regime omega(log^4 n), which is consistent with the imported bounds. The only overlap with a co-author's prior work is [28], used for related-work context and for the definition of edgeFlip; no theorem from [28] is load-bearing in the main proofs. Thus there is no demonstrated circular step, and the appropriate score is 1 reflecting only a minor, non-load-bearing self-citation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on the GRDPG model, on imported spectral concentration bounds for sparse graph embeddings, on the chi-square machinery for local DP lower bounds, and on persistence-diagram stability. No free parameters are fitted to make the theorems work; the only tuning parameters appear in the experimental clustering algorithm. There are no invented entities.

assumptions (4)
  • domain assumption The observed graph A is a generalized random dot-product graph with (p,q)-admissible latent distribution P: rows of X are i.i.d. from P, edges are independent Bernoulli(rho_n X_i^T I_{p,q} X_j), and E(xi_1^T I_{p,q} xi_2) = 1 fixes the scale.
    This is the entire statistical model; the scale condition is needed to identify rho_n and is standard in the cited literature [2,44].
  • ad hoc to paper The spectral embedding concentration results of Rubin-Delanchy et al. [56] and Cape et al. [10], and the improvement in Agterberg et al.
    Theorem 3.3 proof Step 1 uses Lei-Rinaldo [41, Theorem 5.2] and [56, Lemma 12] on this shifted, non-Bernoulli matrix; this transfer is not fully justified and may require an effective sparsity condition n sigma^2 rho_n of order omega(log^4 n).
  • domain assumption The epsilon-edgeLDP lower bound uses [42, Lemma B.1] to control the chi-square integral under the condition epsilon <= min(1, 1/(4 P_{0,ij})), and the finite-reduction matrices X_k remain (p,q)-admissible for small eta.
    Both conditions are asserted rather than fully derived in the paper; they restrict the lower bound to the high-privacy regime epsilon < 3 rho_n / 8.
  • standard math Stability of persistence diagrams in the bottleneck distance under Hausdorff perturbation (Theorem D.1) and invariance of persistence diagrams under Euclidean orthogonal transformations (equation 36) hold as stated.
    Theorem 3.4 proof applies these facts; the invariance is only valid for O(d), which is the source of the proof gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy." pith.science (2026). https://pith.science/paper/XIUAE3LE

@misc{pith2026250417274,
  author       = {Pith},
  title        = {Pith review of: Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XIUAE3LE}},
  note         = {Machine review of arXiv:2504.17274}
}
abstract

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.

Figures

Figures reproduced from arXiv: 2504.17274 by the authors.

Figure 1
Figure 1. Hierarchy of network models. this requires (i) a judicious choice of ε, (ii) optimal algorithms for sanitizing sensitive information, and (iii) appropriate adjustments in the resulting statistical in￾ference to account for privacy. It is well known that there is no free lunch in DP, and that “any meaningful privacy–utility guarantees must come with reasonable assumptions on the data generating mechanism” [39, Sectio… view at source ↗
Figure 2
Figure 2. Illustration of Theorem 3.1. Spectral embedding of Mε(A) after edgeFlip when X∼P =Unif(S 1 ) and ρn ≡1. 3 Main Results This section presents the main results, and the proofs for the main results are collected in Appendix C. 3.1 Closure of GRDPGs under edgeFlip The key insight in the remaining sections comes from the following result, which states that the class of GRDPGs is closed under edgeFlip. Theorem 3.1. Suppos… view at source ↗
Figure 3
Figure 3. Illustration of edgeFlip for SBM(n; γ, ρn) In the absence of privacy, however, the detection thresh￾old for exact recovery requires γρn = Ω log n n  . Compared to (7), the nature of edgeFlip leads to an am￾plification of the effect due to sparsity ρn, and coincides with the observations in [28, p. 13] for weak recovery. A similar analysis can be carried out for ε-edge LDP exact recovery from SBMs with k-communitie… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Illustration of the bounds in Theorem 3.3. Heatmap of d2,∞(Xq , X) error for ε vs. n in Experiment 3.1. and geometric information underlying X. To this end, we use tools from topological data analysis (TDA). Owing to length constraints, we provide an accessible overvie…
Figure 5
Figure 5. Figure 5: Spectral embedding followed by UMAP for the OpenFlights network in Experiment [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Recovery of topological information for the setup in Experiment [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: Performance of spectral methods alongside SDP-based methods in Experiment [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: Illustration of a Dgm(X) computed on a point-cloud in X ∈ R n×d using the Čech filtration. D.1 Additional details on Topology-aware clustering Chazal et al. [13] proposed ToMATo clustering as an algorithm to overcome the drawbacks of k−means clustering by forming clust…
Figure 9
Figure 9. Figure 9: Filtered points in the persistence diagrams for topology-aware clustering for the Two Circles data using [PITH_FULL_IMAGE:figures/full_fig_p032_9.png]
Figure 10
Figure 10. Figure 10: Representative cycles and topology-aware clustering for the Two Circles data. [PITH_FULL_IMAGE:figures/full_fig_p032_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 70 canonical work pages

  1. [1]

    Abbe, E. (2017). Community detection and stochas- tic block models: recent developments.Journal of Machine Learning Research, 18(1):6446–6531

    work page 2017

  2. [2]

    Agterberg, J., Tang, M., and Priebe, C. (2020a). Nonparametric two-sample hypothesis testing for random graphs with negative and repeated eigenval- ues. arXiv preprint arXiv:2012.09828

    arXiv 2020

  3. [3]

    Agterberg, J., Tang, M., and Priebe, C. E. (2020b). On two distinct sources of nonidentifiability in la- tent position random graph models.arXiv preprint arXiv:2003.14250

    arXiv 2020

  4. [4]

    M., Blei, D

    Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008). Mixed membership stochastic blockmodels. Journal of Machine Learning Research

    work page 2008

  5. [5]

    Asoodeh, S., Aliakbarpour, M., and Calmon, F. P. (2021). Local differential privacy is equivalent to contraction of anf-divergence. In 2021 IEEE Inter- national Symposium on Information Theory (ISIT), pages 545–550. IEEE

    work page 2021

  6. [6]

    E., Tang, M., Priebe, C

    Athreya, A., Fishkind, D. E., Tang, M., Priebe, C. E., Park, Y., Vogelstein, J. T., Levin, K., Lyzinski, V., and Qin, Y. (2017). Statistical inference on random dot product graphs: A survey.The Journal of Machine Learning Research, 18(1):8393–8484

    work page 2017

  7. [7]

    Backstrom, L., Dwork, C., and Kleinberg, J. (2007). Wherefore art thou R3579X? anonymized social net- works, hidden patterns, and structural steganogra- phy. InProceedings of the 16th international confer- ence on World Wide Web, pages 181–190

    work page 2007

  8. [8]

    Barber, R. F. and Duchi, J. C. (2014). Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451

    arXiv 2014

Show all 77 references
  1. [9]

    and Niyogi, P

    Belkin, M. and Niyogi, P. (2003). Laplacian eigen- maps for dimensionality reduction and data repre- sentation. Neural Computation, 15(6):1373–1396

    2003

  2. [10]

    Cape, J., Tang, M., and Priebe, C. E. (2019). The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics.The Annals of Statistics, 47(5):2405–2439

    2019

  3. [11]

    Chakraborty, A., Chatterjee, S., and Nandy, S. (2024). PriME: Privacy-aware membership profile estimation in networks. arXiv preprint arXiv:2406.02794

    2024

  4. [12]

    (2016).The Structure and Stability of Persistence Modules

    Chazal, F., De Silva, V., Glisse, M., and Oudot, S. (2016).The Structure and Stability of Persistence Modules. Springer

    2016

  5. [13]

    J., Oudot, S

    Chazal, F., Guibas, L. J., Oudot, S. Y., and Skraba, P. (2013). Persistence-based clustering in Riemannianmanifolds. Journal of the ACM (JACM), 60(6):1–38

    2013

  6. [14]

    and Michel, B

    Chazal, F. and Michel, B. (2017). An introduc- tion to topological data analysis: Fundamental and practical aspects for data scientists.arXiv preprint arXiv:1710.04019

    2017 arXiv

  7. [15]

    Chen, H., Cohen-Addad, V., d’Orsi, T., Epasto, A., Imola, J., Steurer, D., and Tiegel, S. (2023). Private estimation algorithms for stochastic block models and mixture models. Advances in Neural Information Processing Systems, 36:68134–68183

    2023

  8. [16]

    C., Jordan, M

    Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013). Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Founda- tions of Computer Science, pages 429–438. IEEE

    2013

  9. [17]

    C., Jordan, M

    Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2018). Minimax optimal procedures for locally pri- vate estimation.Journal of the American Statistical Association, 113(521):182–201

    2018

  10. [18]

    Dwork, C., Kohli, N., and Mulligan, D. (2019). Differentialprivacyinpractice: Exposeyourepsilons! Journal of Privacy and Confidentiality, 9(2)

    2019

  11. [19]

    Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography Conference, pages 265–284. Springer

    2006

  12. [20]

    Dwork, C., Roth, A., et al. (2014). The algorith- mic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3– 4):211–407

    2014

  13. [21]

    and Harer, J

    Edelsbrunner, H. and Harer, J. (2010). Com- putational Topology: An Introduction. American Mathematical Society

    2010

  14. [22]

    C., Raskhodnikova, S., and Smith, A

    Eden, T., Liu, Q. C., Raskhodnikova, S., and Smith, A. D. (2023). Triangle counting with local edge differential privacy. InInternational Colloquium on Automata, Languages, and Programming

    2023

  15. [23]

    Y., and Zhou, H

    Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2018). Community detection in degree-corrected block models. The Annals of Statistics, 46(5):2153– 2185

    2018

  16. [24]

    and Leskovec, J

    Grover, A. and Leskovec, J. (2016). node2vec: Scalable feature learning for networks. InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855–864

    2016

  17. [25]

    Hajek, B., Wu, Y., and Xu, J. (2016). Achiev- ing exact cluster recovery threshold via semidefinite programming. IEEE Transactions on Information Theory, 62(5):2788–2797

    2016

  18. [26]

    Hay, M., Li, C., Miklau, G., and Jensen, D. (2009). Accurate estimation of the degree distribution of private networks. In2009 Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE. Siddharth Vishwanath & Jonathan Hehir

    2009

  19. [27]

    He, W., Fichtenberger, H., and Peng, P. (2024). A differentially private clustering algorithm for well- clustered graphs. InThe Twelfth International Con- ference on Learning Representations

    2024

  20. [28]

    Hehir, J., Slavković, A., and Niu, X. (2022). Con- sistent spectral clustering of network block models under local differential privacy.Journal of Privacy and Confidentiality, 12(2)

    2022

  21. [29]

    D., Raftery, A

    Hoff, P. D., Raftery, A. E., and Handcock, M. S. (2002). Latent space approaches to social network analysis. Journal of the American Statistical Associ- ation, 97(460):1090–1098

    2002

  22. [30]

    W., Laskey, K

    Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps.Social Networks, 5(2):109–137

    1983

  23. [31]

    Horn, R. A. and Johnson, C. R. (2012).Matrix Analysis. Cambridge University Press

    2012

  24. [32]

    Imola, J., Murakami, T., and Chaudhuri, K. (2021). Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium (USENIX Security ’21)

    2021

  25. [33]

    Jiang, H., Pei, J., Yu, D., Yu, J., Gong, B., and Cheng, X. (2021). Applications of differential pri- vacy in social network analysis: A survey. IEEE Transactions on Knowledge and Data Engineering

    2021

  26. [34]

    and Newman, M

    Karrer, B. and Newman, M. E. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1):016107

    2011

  27. [35]

    N., and Slavković, A

    Karwa, V., Krivitsky, P. N., and Slavković, A. B. (2017). Sharing social network data: Differentially private estimation of exponential family random- graph models. Journal of the Royal Statistical Soci- ety. Series C: Applied Statistics, 66(3):481–500

    2017

  28. [36]

    Karwa, V., Raskhodnikova, S., Smith, A., and Yaroslavtsev, G. (2011). Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146–1157

    2011

  29. [37]

    and Slavković, A

    Karwa, V. and Slavković, A. (2016). Inference us- ing noisy degrees: Differentially privateβ-model and synthetic graphs.The Annals of Statistics, 44(1):87– 112

    2016

  30. [38]

    P., Lee, H

    Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. (2011). What can we learn privately? SIAM Journal on Computing, 40(3):793–826

    2011

  31. [39]

    and Machanavajjhala, A

    Kifer, D. and Machanavajjhala, A. (2011). No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pages 193–204

    2011

  32. [40]

    Afastpersistence-basedsegmen- tation of noisy2d clouds with provable guarantees

    Kurlin, V.(2016). Afastpersistence-basedsegmen- tation of noisy2d clouds with provable guarantees. Pattern Recognition Letters, 83:3–12

    2016

  33. [41]

    and Rinaldo, A

    Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models.The Annals of Statistics, 43(1):215–237

    2015

  34. [42]

    Li, M., Berrett, T., and Yu, Y. (2022). Network change point localisation under local differential pri- vacy. Advances in Neural Information Processing Systems, 35:15013–15026

    2022

  35. [43]

    Li, Y., Purcell, M., Rakotoarivelo, T., Smith, D., Ranbaduge, T., and Ng, K. S. (2023). Private graph data release: A survey.ACM Computing Surveys, 55(11):1–39

    2023

  36. [44]

    and Sarkar, P

    Lunde, R. and Sarkar, P. (2023). Subsam- pling sparse graphons under minimal assumptions. Biometrika, 110(1):15–32

    2023

  37. [45]

    L., Tang, M., Athreya, A., and Priebe, C

    Lyzinski, V., Sussman, D. L., Tang, M., Athreya, A., and Priebe, C. E. (2014). Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electronic Journal of Statistics, 8:2905– 2922

    2014

  38. [46]

    McInnes, L., Healy, J., and Melville, J. (2018). UMAP: Uniform manifold approximation and pro- jection for dimension reduction. arXiv preprint arXiv:1802.03426

    2018 arXiv

  39. [47]

    S., Nguyen, D., Vullikanti, A., and Tandon, R

    Mohamed, M. S., Nguyen, D., Vullikanti, A., and Tandon, R. (2022). Differentially private commu- nity detection for stochastic block models. InIn- ternational Conference on Machine Learning, pages 15858–15894. PMLR

    2022

  40. [48]

    Mülle, Y., Clifton, C., and Böhm, K. (2015). Privacy-integrated graph clustering through differ- ential privacy. InEDBT/ICDT Workshops, pages 247–254

    2015

  41. [49]

    Narayanan, A., Shi, E., and Rubinstein, B. I. (2011). Link prediction by de-anonymization: How we won the Kaggle social network challenge. In The 2011 International Joint Conference on Neural Networks, pages 1825–1834. IEEE

    2011

  42. [50]

    and Shmatikov, V

    Narayanan, A. and Shmatikov, V. (2008). Robust de-anonymization of large sparse datasets. In2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111–125

    2008

  43. [51]

    and Vullikanti, A

    Nguyen, D. and Vullikanti, A. K. (2024). Differ- entially private exact recovery for stochastic block models. In Forty-first International Conference on Machine Learning

    2024

  44. [52]

    Perozzi, B., Al-Rfou, R., and Skiena, S. (2014). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD interna- tional conference on Knowledge discovery and data mining, pages 701–710

    2014

  45. [53]

    Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., and Ren, K. (2017). Generating synthetic decentral- Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy ized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Confer...

    2017

  46. [54]

    and Steinberger, L

    Rohde, A. and Steinberger, L. (2020). Ge- ometrizing rates of convergence under local differ- ential privacy constraints.The Annals of Statistics, 48(5):2646–2670

    2020

  47. [55]

    Rubin-Delanchy, P. (2020). Manifold structure in graph embeddings. Advances in Neural Information Processing Systems, 33

    2020

  48. [56]

    Rubin-Delanchy, P., Cape, J., Tang, M., and Priebe, C. E. (2022). A statistical interpretation of spectral embedding: The generalised random dot product graph. Journal of the Royal Statistical So- ciety Series B: Statistical Methodology, 84(4):1446– 1473

    2022

  49. [57]

    Solanki, V., Rubin-Delanchy, P., and Gallagher, I. (2019). Persistent homology of graph embeddings. arXiv preprint arXiv:1912.10238v1

    2019 arXiv

  50. [58]

    Anintroductiontomatrixcon- centration inequalities.Foundations and Trends® in Machine Learning, 8(1-2):1–230

    Tropp, J.A.(2015). Anintroductiontomatrixcon- centration inequalities.Foundations and Trends® in Machine Learning, 8(1-2):1–230

    2015

  51. [59]

    Tsybakov, A. B. (2008).Introduction to Nonpara- metric Estimation. Springer Publishing Company, Incorporated, 1st edition

    2008

  52. [60]

    Warner, S. L. (1965). Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63–69

    1965

  53. [61]

    Wasserman, L. (2018). Topological data analy- sis. Annual Review of Statistics and Its Application, 5:501–532

    2018

  54. [62]

    and Levin, K

    Yan, H. and Levin, K. (2023). Minimax rates for latent position estimation in the generalized random dot product graph.arXiv preprint arXiv:2307.01942

    2023 arXiv

  55. [63]

    Yu, B. (1997). Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam: Research papers in probability and statistics, pages 423–435. Springer

    1997

  56. [64]

    Zhang, A. Y. and Zhou, H. H. (2016). Minimax rates of community detection in stochastic block models. The Annals of Statistics, 44(5):2252–2280. Checklist

    2016

  57. [65]

    [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm

    For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [No] The time/space c...

  58. [66]

    [Yes] (b) Complete proofs of all theoretical results

    For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes]

  59. [67]

    [Yes] https://github.com/sidv23/grdpg-ldp (b) All the training details (e.g., data splits, hy- perparameters, how they were chosen)

    For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to re- produce the main experimental results (either in the supplemental material or as a URL). [Yes] https://github.com/sidv23/grdpg-ldp (b) All the tr...

  60. [68]

    [Not Applicable] (b) The license information of the assets, if appli- cable

    If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if appli- cable. [Not Applicable] (c)...

  61. [69]

    ∆P and ∆Q are both positive definite

  62. [70]

    Ifλ1(∆P)≥λ2(∆P)≥···≥ λd(∆P) are the eigenvalues of∆P, andλ1(∆Q)≥λ2(∆Q)≥···≥ λd+1(∆Q) are the eigenvalues of∆Q, then λ1(∆Q)≥σ2(ε)λ1(∆P)≥···≥ σ(ε)2λd(∆P)≥λd+1(∆Q)

  63. [71]

    For sufficiently smallε> 0, there existsC1 > 0 such that λ1(∆Q)≤τ (ε)2 +C1σ(ε)τ (ε)

  64. [72]

    For sufficiently smallε> 0, there existsC2 > 0 such that λd+1(∆Q)≥C2σ2(ε). Proof. For notational simplicity, throughout the proof we takeσ =σ(ε) and τ =τ (ε). Part 1. Forξ∼ P, ξξTis positive definite a.e.-P. To see this, note that for anyx∈ Rd, xT ξξT x = xTξ ≥ 0 a.e.− P. It f...

  65. [73]

    Up to a collection of repeated zero eigenvalues, Λ(PY) = Λ YTYIp+1,q = Λ YTY −1/2 Ip+1,q YTY −1/2

  66. [74]

    With probability greater than1− 2(d + 1)/n, YTYIp+1,q−n∆QIp+1,q ≤C p n logn

  67. [75]

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

    |λd+1(PY)| = ΩP nσ2(ε) . Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy Proof. As before, for notational simplicity throughout the proof we takeσ =σ(ε) and τ =τ (ε). Part 1. The first claim follows from the same argument as in Fact A.3. Part 2....

  68. [76]

    λmin(∆Q) = Ω(σ(ε)2) andλmax(∆Q) =O(1)

  69. [77]

    ForMε(A) =: AY∼G (Y;p+1,q ), next lemma establishes a tail bound for∥AY− PY∥ using a straightforward application of Lei and Rinaldo [41, Theorem 5.2]

    λmin(PY) = Ω(nσ(ε)2) andλmax(PY) = Θ(λmax(PX)). ForMε(A) =: AY∼G (Y;p+1,q ), next lemma establishes a tail bound for∥AY− PY∥ using a straightforward application of Lei and Rinaldo [41, Theorem 5.2]. Lemma B.3. Under the conditions of Theorem B.1, there exists a constantC >0 su...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.