[2505.03858] Differentially Private and Scalable Estimation of the Network Principal Component

Computer Science > Data Structures and Algorithms arXiv:2505.03858 (cs) [Submitted on 6 May 2025 (v1), last revised 5 Mar 2026 (this version, v2)] Title:Differentially Private and Scalable Estimation of the Network Principal Component Authors:Alireza Khayatian, Anil Vullikanti, Aritra Konar View a PDF of the paper titled Differentially Private and Scalable Estimation of the Network Principal Component, by Alireza Khayatian and 1 other authors View PDF HTML (experimental) Abstract: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) framew...