# Differentially Private and Scalable Estimation of the Network Principal Component

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 73 references that are in the map.
- First posted on arXiv 6 May 2025.

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

- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [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)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread](https://mlsanity.com/paper/1501.06614/) (2015)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Differentially Private Densest Subgraph](https://mlsanity.com/paper/2106.00508/) (2021)
- [Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs](https://mlsanity.com/paper/2211.10887/) (2022)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [The Densest Subgraph Problem with a Convex/Concave Size Function](https://mlsanity.com/paper/1703.03603/) (2017)
- [Unveiling Privacy Vulnerabilities: Investigating the Role of Structure in Graph Data](https://mlsanity.com/paper/2407.18564/) (2024)
- [Exploring the Subgraph Density-Size Trade-off via the Lov'asz Extension](https://mlsanity.com/paper/2102.03434/) (2021)
- [Almost Tight Bounds for Differentially Private Densest Subgraph](https://mlsanity.com/paper/2308.10316/) (2023)

## Abstract (arXiv)

Computing the principal component (PC) of the adjacency matrix of an undirected graph has several applications ranging from identifying key vertices for influence maximization and controlling diffusion processes, to discovering densely interconnected vertex subsets. However, many networked datasets are sensitive, which necessitates private computation of the PC for use in the aforementioned applications. Differential privacy has emerged as the gold standard in privacy-preserving data analysis, but existing DP algorithms for private PC suffer from low accuracy due to large noise injection or high complexity. Motivated by the large gap between the local and global sensitivities of the PC on real-graphs, we consider instance-specific mechanisms for privately computing the PC under edge-DP. These mechanisms guarantee privacy for all datasets, but provide good utility on ``well-behaved'' datasets by injecting smaller amounts of noise. More specifically, we consider the Propose-Test-Release (PTR) framework. Although computationally expensive in general, we design a novel approach for implementing a PTR variant in the same time as computation of a non-private PC, while offering good utility. Our framework tests in a differentially-private manner whether a given graph is ``well-behaved'' or not, and then tests whether its private to release a noisy PC with small noise. As a consequence, this also leads to the first DP algorithm for the Densest-k-subgraph problem, a key graph mining primitive. We run our method on diverse real-world networks, with the largest having 3 million vertices, and compare its utility to a pre-existing baseline based on the private power method (PPM). Although PTR requires a slightly larger privacy budget, on average, it achieves a 180-fold improvement in runtime over PPM.