University of North Carolina at Chapel Hill (Kenan-Flagler)
In this paper, the authors focus on differential privacy preserving spectral graph analysis. Spectral graph analysis deals with the analysis of the spectra (eigenvalues and eigenvector components) of the graph's adjacency matrix or its variants. They develop two approaches to computing the differential eigen decomposition of the graph's adjacency matrix. The first approach, denoted as LNPP, is based on the laplace mechanism that calibrates laplace noise on the eigenvalues and every entry of the eigenvectors based on their sensitivities. They derive the global sensitivities of both eigenvalues and eigenvectors based on the matrix perturbation theory.