CONSISTENT SPECTRAL CLUSTERING OF NETWORK BLOCK MODELS UNDER LOCAL DIFFERENTIAL PRIVACY

Abstract

The stochastic block model (SBM) and degree-corrected block model (DCBM) are network models often selected as the fundamental setting in which to analyze the theoretical properties of community detection methods. We consider the problem of spectral clustering of SBM and DCBM networks under a local form of edge differential privacy. Using a randomized response privacy mechanism called the edge-flip mechanism, we develop theoretical guarantees for differentially private community detection, demonstrating conditions under which this strong privacy guarantee can be upheld while achieving spectral clustering convergence rates that match the known rates without privacy. We prove the strongest theoretical results are achievable for dense networks (those with node degree linear in the number of nodes), while weak consistency is achievable under mild sparsity (node degree greater than $\sqrt{n}$). We empirically demonstrate our results on a number of network examples.

Keywords: community detection; differential privacy; spectral clustering; stochastic block model.

Figure 1:

Proportion of misclassified nodes in simulated SBM networks for various values of $\epsilon ,n$. Left (dense): $Y~\text{SSBM}\left(n,k=3,p=0.2,r=0.05\right)$, Right (sparse): $Y~\text{SSBM}\left(n,k=2,p=1.5n^{-.3},r=.15n^{-.3}\right)$

Figure 2:

Proportion of misclassified nodes in simulated DCBM networks for various values of $\epsilon ,n$. Left (dense): $Y~\text{SDCBM}\left(n,k=3,p=0.4,r=0.05,a=0.3\right)$, Right (sparse): $Y~\text{SSBM}\left(n,k=2,p=1.5n^{-.3},r=.15n^{-3}\right)$.

Figure 3:

Trade-off of privacy-loss and accuracy of private spectral clustering on a small dataset, Hansell’s friendship data (Hansell, 1984), with varying privacy-loss $\epsilon$, and “NP” denoting non-private data.

Figure 4:

Trade-off of privacy-loss and accuracy of private spectral clustering on well-known DCBM datasets, with varying privacy-loss $\epsilon$, and “NP” denoting non-private data. Left: Facebook friendships of Simmons College students (Traud et al., 2012), Right: political blogs network (Adamic and Glance, 2005)

Figure 5:

Visualization of congressional voting networks for 70th U.S. Senate (left) and 110th U.S. Senate (right). Democrats are depicted as blue nodes and Republican as red.

Figure 6:

Trade-off of privacy-loss and accuracy of private spectral clustering on U.S. Congressional voting networks. Clockwise from top left: 110th House of Representatives, 70th House of Representatives, 70th Senate, 110th Senate