pith. sign in

arxiv: 2510.07136 · v2 · submitted 2025-10-08 · 💻 cs.IT · cs.CR· cs.LG· cs.SI· math.IT

Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency

Antti Koskela , Mohamed Seif , H. Vincent Poor , Andrea J. Goldsmith This is my paper

Pith reviewed 2026-05-18 08:53 UTC · model grok-4.3

classification 💻 cs.IT cs.CRcs.LGcs.SImath.IT
keywords differential privacyspectral clusteringgraph clusteringmatrix shufflingedge differential privacymisclassification ratecommunity detectioneigengap
0
0 comments X

The pith

Matrix shuffling after edge flipping makes private spectral graph clustering accurate with error rates that improve as networks grow.

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

The paper develops a matrix shuffling mechanism for spectral graph clustering that satisfies edge differential privacy while delivering better accuracy on large graphs. Randomized edge flipping alone gives only constant privacy, but adding a random permutation of the matrix entries amplifies privacy so the effective budget shrinks with the number of nodes. A unified analysis using Davis-Kahan perturbation theory and a classification margin bound then shows that this mechanism produces misclassification error scaling as Õ(1/n). The same framework recovers the worse Õ(1) scaling for the standard Gaussian mechanism on the adjacency matrix and for the noisy power method. Experiments on synthetic and real networks confirm that the theoretical scaling holds when the graph has a clear eigengap.

Core claim

The matrix shuffling mechanism, formed by applying randomized edge flipping followed by a random permutation to the adjacency matrix, achieves an error rate scaling of Õ(1/n) under edge differential privacy for spectral clustering, outperforming the Analyze Gauss and noisy power method baselines that scale as Õ(1) in the number of nodes.

What carries the argument

The matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix to amplify privacy as graph size grows.

If this is right

  • Misclassification rates for all considered mechanisms are explicitly bounded in terms of the privacy budget, eigengap, and number of communities.
  • The effective privacy parameter tends to zero with growing graph size, allowing accurate community recovery on large networks.
  • A separate private spectral gap detection procedure can estimate the number of communities without extra privacy cost.
  • The same Davis-Kahan plus margin analysis applies uniformly to multiple private spectral methods.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The scaling improvement could make privacy-preserving community detection practical for very large social or biological networks where adding nodes naturally strengthens privacy.
  • The approach may extend to other eigenvector-based tasks such as graph embedding or semi-supervised learning under similar privacy constraints.
  • For networks whose size increases over time, the mechanism could be applied incrementally with accumulating privacy amplification.
  • Empirical tests on dynamic graphs would reveal whether the 1/n scaling persists when edges arrive sequentially.

Load-bearing premise

The graph must possess a sufficient eigengap between the leading eigenvalues so that privacy noise does not prevent the recovered eigenvectors from separating the communities.

What would settle it

Measuring misclassification error on large synthetic graphs with a clear eigengap and checking whether the shuffling mechanism's error decreases proportionally to 1/n while the two baseline mechanisms remain flat.

Figures

Figures reproduced from arXiv: 2510.07136 by Andrea J. Goldsmith, Antti Koskela, H. Vincent Poor, Mohamed Seif.

Figure 1
Figure 1. Figure 1: Synopsis of results for the three different mechanisms: error rate vs. [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: Eigenvalues of the perturbed and adjacency matrix that is similarity transformed with [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Ablation on the number of iterations N in the noisy power method across all four datasets. Each figure reports error rate as a function of N, averaged over 50 runs. C.2 Ablation on Iteration Length of the Noisy Power Method Here, we present an ablation study on the effect of the iteration length N in the noisy power method. The number of iterations N governs the trade-off between accuracy and computational… view at source ↗
Figure 4
Figure 4. Figure 4: Ablation on the projection dimension m for the matrix projection method. Results are reported for the two datasets where the mechanism is effective. C.3 Ablation on Projection Dimension for the Matrix Projection Method We next investigate the effect of the projection dimension m in the matrix projection mechanism, which reduces the adjacency matrix A ∈ {0, 1} n×n to a sketch AQ ∈ R n×m before adding Gaussi… view at source ↗
read the original abstract

We study spectral graph clustering under edge differential privacy. We propose a matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix. While edge flipping alone provides only a constant $\varepsilon$ guarantee as the graph grows, shuffling amplifies privacy so that the effective $\varepsilon$ tends to zero with the number of nodes. We develop a unified error analysis framework -- based on Davis--Kahan perturbation theory and a classification-margin bound -- that gives explicit misclassification rates for all the mechanisms considered as a function of the privacy budget, eigengap, and number of communities. Applying this framework, we show that the matrix shuffling mechanism achieves an error rate scaling of $\tilde{O}(1/n)$, a clear improvement over two canonical DP baselines from the private PCA literature: the Gaussian mechanism applied directly to the adjacency matrix (Analyze Gauss) and the noisy power method, both of which scale as $\tilde{O}(1)$ in $n$. We further propose a private spectral gap detection algorithm for estimating the number of communities. Experiments on synthetic and real-world networks validate our theoretical findings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper proposes a matrix shuffling mechanism for edge-differentially private spectral graph clustering that augments randomized edge flipping with a random permutation of the adjacency matrix. This yields privacy amplification with effective ε tending to zero as n grows. A unified error analysis based on Davis-Kahan perturbation theory and a classification-margin bound supplies explicit misclassification rates for the proposed mechanism and two baselines (Analyze Gauss and the noisy power method) as functions of the privacy budget, eigengap δ, and number of communities k. The central claim is that the shuffling mechanism attains an Õ(1/n) error rate, improving on the Õ(1) scaling of the baselines. The work also presents a private spectral-gap detection procedure for estimating k and reports experiments on synthetic and real networks.

Significance. If the stated conditions on the eigengap hold, the result supplies a concrete improvement in the accuracy-privacy tradeoff for spectral clustering, with error rates that decrease in n rather than remaining constant. The unified analysis framework permits direct comparison across mechanisms, and the experimental validation on both synthetic SBM graphs and real networks lends support to the theoretical predictions. The work therefore addresses a practically relevant scaling question in private graph analysis.

major comments (2)
  1. [§4.2] §4.2 (Theorem 4.3 and surrounding Davis-Kahan + margin analysis): The Õ(1/n) misclassification rate for the shuffling mechanism is obtained only when the effective perturbation norm σ after flipping and permutation satisfies σ = o(δ), so that the sin Θ bound is small enough for the margin argument to deliver per-node error O(1/n). The manuscript states rates explicitly in terms of δ, ε and k, yet does not delineate the SBM parameter regime (e.g., community separation p-q relative to n) that guarantees δ = ω(σ) asymptotically; this assumption is load-bearing for the headline scaling improvement over the Õ(1) baselines.
  2. [§5] §5 (experimental validation): The synthetic graphs used to illustrate the Õ(1/n) scaling are generated with fixed community parameters; without reporting the realized eigengap values or verifying that they lie in the regime where δ dominates the privacy-induced noise, the experiments do not confirm that the observed improvement corresponds to the theoretical condition required for the claimed rate.
minor comments (3)
  1. [Abstract] The abstract asserts a 'clear improvement' without qualifying that the Õ(1/n) rate presupposes a sufficiently large eigengap relative to residual noise; a brief parenthetical would improve precision.
  2. [§3.2] §3.2: The matrix-shuffling procedure would be easier to follow if accompanied by a short pseudocode block listing the sequence of flipping, permutation, and noise addition steps.
  3. [§4] Notation for the effective privacy parameter after amplification is introduced in §3 but reused without redefinition in the error bounds of §4; a single consolidated definition would reduce reader effort.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. The comments highlight important points for clarifying the theoretical conditions and strengthening the experimental validation. We address each major comment below and will make the suggested revisions to improve the paper.

read point-by-point responses

  1. Referee: [§4.2] §4.2 (Theorem 4.3 and surrounding Davis-Kahan + margin analysis): The Õ(1/n) misclassification rate for the shuffling mechanism is obtained only when the effective perturbation norm σ after flipping and permutation satisfies σ = o(δ), so that the sin Θ bound is small enough for the margin argument to deliver per-node error O(1/n). The manuscript states rates explicitly in terms of δ, ε and k, yet does not delineate the SBM parameter regime (e.g., community separation p-q relative to n) that guarantees δ = ω(σ) asymptotically; this assumption is load-bearing for the headline scaling improvement over the Õ(1) baselines.

    Authors: We agree that explicitly delineating the SBM parameter regime ensuring δ = ω(σ) would make the conditions for the Õ(1/n) scaling clearer. In the revised manuscript, we will add a remark or corollary after Theorem 4.3 specifying sufficient conditions on the SBM parameters (such as p − q = Ω(√(log n / n)) for appropriate privacy budgets) under which the eigengap asymptotically dominates the effective noise σ. This will explicitly connect the headline rate to standard SBM assumptions without altering the existing theorems. revision: yes

  2. Referee: [§5] §5 (experimental validation): The synthetic graphs used to illustrate the Õ(1/n) scaling are generated with fixed community parameters; without reporting the realized eigengap values or verifying that they lie in the regime where δ dominates the privacy-induced noise, the experiments do not confirm that the observed improvement corresponds to the theoretical condition required for the claimed rate.

    Authors: We acknowledge the value of reporting realized eigengap values to confirm the theoretical regime. In the revised Section 5, we will include the computed eigengaps δ for the synthetic SBM instances, along with the corresponding effective perturbation norms σ induced by the privacy mechanisms. We will add a brief verification note or table entry confirming that δ = ω(σ) holds in the reported experiments, thereby linking the empirical results directly to the conditions required for the Õ(1/n) scaling. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central error-rate claims are obtained by applying the external Davis-Kahan theorem to bound eigenvector perturbation by the effective noise after shuffling, followed by a standard margin-based misclassification argument. Both the Õ(1/n) scaling for the shuffling mechanism and the Õ(1) baselines follow directly from how the privacy noise term behaves with n under the stated eigengap assumption; no quantity is defined in terms of itself, no parameter is fitted to a subset and then relabeled as a prediction, and no load-bearing step reduces to a self-citation. The analysis is therefore self-contained against the cited external theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on the standard Davis-Kahan theorem and a classification margin argument; no new free parameters are introduced beyond the usual privacy budget ε and the graph's eigengap, which are treated as inputs rather than fitted quantities. No invented entities are postulated.

axioms (2)
  • standard math Davis-Kahan perturbation theorem applies to the noisy shuffled adjacency matrix
    Invoked to bound eigenvector deviation as a function of the noise level induced by the privacy mechanism.
  • domain assumption The graph satisfies a sufficient eigengap condition relative to the privacy noise
    Required for the perturbation bound to translate into a useful misclassification guarantee.

pith-pipeline@v0.9.0 · 5740 in / 1610 out tokens · 27331 ms · 2026-05-18T08:53:13.839023+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 1 internal anchor

  1. [1]

    Community detection and stochastic block models: recent developments

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

    work page 2017

  2. [2]

    Community detection and stochastic block models: Recent developments

    Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2017

    work page 2017

  3. [3]

    Entrywise eigenvector analysis of random matrices with low expected rank.Annals of Statistics, 48(3):1452, 2020

    Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank.Annals of Statistics, 48(3):1452, 2020. 27

    work page 2020

  4. [4]

    Differentially private data analysis of social networks via restricted sensitivity

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. InProceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, page 87–96, New York, NY, USA,

    work page

  5. [5]

    Association for Computing Machinery

    work page

  6. [6]

    Differentially private data analysis of social networks via restricted sensitivity

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. InProceedings of the 4th Conference on Innovations in Theoretical Computer Science, pages 87–96, 2013

    work page 2013

  7. [7]

    Hongjie Chen, Vincent Cohen-Addad, Tommaso d’Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel. Private estimation algorithms for stochastic block models and mixture models.Proceedings of the 2023 Advances in Neural Information Processing Systems (NeurIPS), 36:68134–68183, 2023

    work page 2023

  8. [8]

    Spectral methods for data science: A statistical perspective.Foundations and Trends®in Machine Learning, 14(5):566–806, 2021

    Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: A statistical perspective.Foundations and Trends®in Machine Learning, 14(5):566–806, 2021

    work page 2021

  9. [9]

    Scalable differentially private clustering via hierarchically separated trees

    Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Med- ina, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hierarchically separated trees. InProceedings of the 28th ACM SIGKDD Confer- ence on Knowledge Discovery and Data Mining, pages 221–230, 2022

    work page 2022

  10. [10]

    Wiley, 2006

    Thomas M Cover and Joy A Thomas.Elements of Information Theory. Wiley, 2006

    work page 2006

  11. [11]

    Cambridge University Press, 2011

    Imre Csisz´ ar and J´ anos K¨ orner.Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011

    work page 2011

  12. [12]

    On the privacy properties of variational inference

    Jinshuo Dong, Aaron Roth, and Kunal Talwar. On the privacy properties of variational inference. Proceedings of the 2022 Advances in Neural Information Processing Systems (NeurIPS), 2022

    work page 2022

  13. [13]

    Now Publishers, 2014

    Cynthia Dwork and Aaron Roth.The Algorithmic Foundations of Differential Privacy. Now Publishers, 2014

    work page 2014

  14. [14]

    The algorithmic foundations of differential privacy.Foun- dations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014

    Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy.Foun- dations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014

    work page 2014

  15. [15]

    Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, and Peilin Zhong. Dif- ferentially private graph learning via sensitivity-bounded personalized pagerank.Proceedings of the 2022 Advances in Neural Information Processing Systems (NeurIPS), 35:22617–22627, 2022

    work page 2022

  16. [16]

    Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. InProceedings of the IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954–964, 2022

    work page 2022

  17. [17]

    Stronger privacy amplification by shuffling for R´ enyi and approximate differential privacy

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for R´ enyi and approximate differential privacy. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966–4981. SIAM, 2023

    work page 2023

  18. [18]

    Stronger privacy amplification by shuffling for R´ enyi and approximate differential privacy.arXiv preprint arXiv:2208.04591, 2023

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for R´ enyi and approximate differential privacy.arXiv preprint arXiv:2208.04591, 2023. 28

    work page arXiv 2023

  19. [19]

    The noisy power method: A meta algorithm with applications

    Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Proceedings of the 2014 Advances in Neural Information Processing Systems (NeurIPS), 27, 2014

    work page 2014

  20. [20]

    Consistent spectral clustering of network block models under local differential privacy.The Journal of privacy and confidentiality, 12(2), 2022

    Jonathan Hehir, Aleksandra Slavkovi´ c, and Xiaoyue Niu. Consistent spectral clustering of network block models under local differential privacy.The Journal of privacy and confidentiality, 12(2), 2022

    work page 2022

  21. [21]

    Locally differentially private analysis of graph statistics

    Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Locally differentially private analysis of graph statistics. InProceedings of the 30th USENIX Symposium on Security, 2021

    work page 2021

  22. [22]

    The composition theorem for differential privacy.IEEE Transactions on Information Theory, 63(6):4037–4049, 2017

    Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy.IEEE Transactions on Information Theory, 63(6):4037–4049, 2017

    work page 2017

  23. [23]

    Private analysis of graph structure.Proceedings of the VLDB Endowment, 4(11):1146–1157, 2011

    Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure.Proceedings of the VLDB Endowment, 4(11):1146–1157, 2011

    work page 2011

  24. [24]

    Private analysis of graph structure.ACM Transactions on Database Systems (TODS), 39(3):1–33, 2014

    Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure.ACM Transactions on Database Systems (TODS), 39(3):1–33, 2014

    work page 2014

  25. [25]

    Privacy via the Johnson-Lindenstrauss Transform

    Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra. Privacy via the Johnson-Lindenstrauss Transform.arXiv preprint arXiv:1204.2606, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  26. [26]

    Differentially private densest- k-subgraph

    Alireza Khayatian, Anil Vullikanti, and Aritra Konar. Differentially private densest- k-subgraph. arXiv preprint arXiv:2505.03858, 2025

    work page arXiv 2025

  27. [27]

    Numerical accounting in the shuffle model of differential privacy.Transactions on machine learning research, 2023

    Antti Koskela, Mikko A Heikkil¨ a, and Antti Honkela. Numerical accounting in the shuffle model of differential privacy.Transactions on machine learning research, 2023

    work page 2023

  28. [28]

    Concentration and regularization of random graphs.Random Structures & Algorithms, 51(3):538–561, 2017

    Can M Le, Elizaveta Levina, and Roman Vershynin. Concentration and regularization of random graphs.Random Structures & Algorithms, 51(3):538–561, 2017

    work page 2017

  29. [29]

    Consistency of spectral clustering in stochastic block models

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

    work page 2015

  30. [30]

    Learning to discover social circles in ego networks.Proceedings of the 2012 Advances in Neural Information Processing Systems (NeurIPS), 25, 2012

    Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks.Proceedings of the 2012 Advances in Neural Information Processing Systems (NeurIPS), 25, 2012

    work page 2012

  31. [31]

    Spectral partitioning of random graphs

    Frank McSherry. Spectral partitioning of random graphs. InProceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 529–537, 2001

    work page 2001

  32. [32]

    On spectral clustering: Analysis and an algorithm

    Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Proceedings of the 2001 Advances in Neural Information Processing Systems (NeurIPS), 14, 2001

    work page 2001

  33. [33]

    Detecting communities under differential privacy

    Hiep H Nguyen, Abdessamad Imine, and Micha¨ el Rusinowitch. Detecting communities under differential privacy. InProceedings of the 2016 ACM Workshop on Privacy in the Electronic Society, pages 83–93, 2016

    work page 2016

  34. [34]

    Regularized spectral clustering under the degree-corrected stochastic blockmodel.Proceedings of the 2013 Advances in Neural Information Processing Systems (NeurIPS), 26, 2013

    Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel.Proceedings of the 2013 Advances in Neural Information Processing Systems (NeurIPS), 26, 2013. 29

    work page 2013

  35. [35]

    Generating synthetic decentralized social graphs with local differential privacy

    Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. InProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 425–438, 2017

    work page 2017

  36. [36]

    Robust locally differentially private graph analysis

    Amrita Roy Chowdhury, Jacob Imola, and Kamalika Chaudhuri. Robust locally differentially private graph analysis. InProceedings of the 20th ACM Asia Conference on Computer and Communications Security, pages 635–650, 2025

    work page 2025

  37. [37]

    Differentially private commu- nity detection for stochastic block models

    Mohamed Seif, Dung Nguyen, Anil Vullikanti, and Ravi Tandon. Differentially private commu- nity detection for stochastic block models. InProceedings of the 2022 International Conference on Machine Learning (ICML), pages 15858–15894, 2022

    work page 2022

  38. [38]

    Differentially private online community detection for censored block models: Algorithms and fundamental limits

    Mohamed Seif, Liyan Xie, Andrea J Goldsmith, and H Vincent Poor. Differentially private online community detection for censored block models: Algorithms and fundamental limits. IEEE Transactions on Information Forensics and Security, 2025

    work page 2025

  39. [39]

    Collective classification in network data.AI magazine, 29(3):93–93, 2008

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data.AI magazine, 29(3):93–93, 2008

    work page 2008

  40. [40]

    Locally differentially private graph clustering via the power iteration method.arXiv preprint arXiv:2505.11169, 2025

    Vorapong Suppakitpaisarn and Sayan Mukherjee. Locally differentially private graph clustering via the power iteration method.arXiv preprint arXiv:2505.11169, 2025

    work page arXiv 2025

  41. [41]

    Tsybakov.Introduction to Nonparametric Estimation

    Alexandre B. Tsybakov.Introduction to Nonparametric Estimation. Springer, 2009

    work page 2009

  42. [42]

    Cambridge University Press, 2018

    Roman Vershynin.High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018

    work page 2018

  43. [43]

    A tutorial on spectral clustering.Statistics and Computing, 17(4):395–416, 2007

    Ulrike von Luxburg. A tutorial on spectral clustering.Statistics and Computing, 17(4):395–416, 2007

    work page 2007

  44. [44]

    Differentially private subspace clustering

    Yining Wang, Yu-Xiang Wang, and Aarti Singh. Differentially private subspace clustering. Proceddings of the 2015 Advances in Neural Information Processing Systems (NeurIPS), 28, 2015

    work page 2015

  45. [45]

    Differential privacy preserving spectral graph analysis

    Yue Wang, Xintao Wu, and Leting Wu. Differential privacy preserving spectral graph analysis. InPacific-Asia Conference on Knowledge Discovery and Data Mining, pages 329–340. Springer, 2013

    work page 2013

  46. [46]

    Randomized response: A survey technique for eliminating evasive answer bias.Journal of the American Statistical Association, 60(309):63–69, 1965

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

    work page 1965

  47. [47]

    Optimal accounting of differential privacy via characteristic function

    Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. InProceedings of the 2022 International Conference on Artificial Intelligence and Statistics, pages 4782–4817. PMLR, 2022. 30

    work page 2022