1

1

Differential privacy; Propose-Test-Release; Social networks; Spectral method; Community detection.

1 Introduction↩︎

Let \(A\in\{0,1\}^{n\times n}\) be the adjacency matrix of an undirected network on a fixed node set \([n]\), and let \(\ell\in[K]^n\) denote the latent community labels. Spectral community detection estimates \(\ell\) from the leading eigenspace of \(A\) via row normalization and clustering [1]–[4]. In social network applications, the edge \(A_{ij}\) may itself be sensitive. It records whether two individuals maintain a relationship, communication tie, or affiliation. Spectral community labels aggregate the edge pattern into a lower-dimensional structural summary, and this summary contains edge information. Hence, releasing community labels can disclose private edges, especially given auxiliary information about this network.

Differential privacy (DP) formalizes this concern by imposing stability of the output distribution under neighboring datasets [5]. This neighboring relation determines the unit to protect. For ordinary networks, we use edge adjacency: two networks \(A\) and \(A'\) are neighboring if they differ in only one undirected edge. An \((\varepsilon, \delta)\)-edge-DP community detection procedure must release labels whose distribution is insensitive to the choice of \(A\) or \(A'\), and hence insensitive to the presence or absence of any single dyadic relation. Therefore, attackers cannot reveal the edge information based on released labels. This privacy requirement is imposed on the released estimator, not on the network itself.

We also study bipartite community detection. Let \(B\in\{0,1\}^{n\times m}\) record edges between left-side nodes \(U = [n]\) and right-side units \(V = [m]\). The target is to cluster the left-side nodes \(U\) using their connection patterns across \(V\). Such data arise in voting records, user–item interactions, and affiliation networks. In these applications, one unit in \(V\) may represent a roll call, item, or organization, and its column in \(B\) records the full response or connection profile across \(U\). Protecting this profile leads to column-node privacy, which is stronger than protecting a single edge. We therefore define neighboring datasets \(B \sim_N B'\), where \(B\) and \(B'\) differ in one entire column, and we consider the private release of left-side community labels under column-node differential privacy.

A common strategy for private network analysis is to privatize the whole network and then perform any downstream task on it [6], [7]. This approach is broadly applicable, but it is not tailored to specific tasks. When it comes to community detection, such network-level perturbation suffers too heavy noise and becomes statistically inefficient. Randomized edges may distort degree patterns or weaken community separation, especially in sparse or heterogeneous networks. This motivates a private mechanism that acts directly on the spectral estimator rather than on the full network.

The difficulty is that direct privatization requires a uniform sensitivity bound for the empirical spectral embedding. Differential privacy must hold over all neighboring datasets, whereas spectral community detection theory is typically probabilistic. Standard spectral analyses establish eigenspace stability with high probability under a specific network model. Privacy, however, must also control atypical networks with negligible model probability. Such networks may have small eigengaps, irregular degree behavior, or highly coherent empirical eigenvectors, leading to large sensitivity under neighboring changes. Moreover, unlike mean estimation or regression, spectral clustering has no simple projection onto a convex regular domain: the relevant stability conditions involve global and nonconvex properties of the adjacency matrix. This mismatch between probabilistic spectral theory and deterministic privacy requirements is the central obstacle.

We develop NetPTR, an efficient differentially private spectral community detection approach that privatizes the spectral embedding directly. We develop one-edge perturbation analysis for general networks. Based on this analysis, we construct a a computable stability certificate for the observed network. When the certificate indicates local spectral stability, NetPTR releases a noisy empirical eigenspace with noise calibrated to the certified local sensitivity; otherwise, the method returns a data-independent output. This mechanism allows us to connect the differential privacy requirement on all datasets and the spectral community detection theory on regular datasets.

1.1 Our Contributions↩︎

We propose NetPTR to protect one edge for ordinary networks and Bi-NetPTR to protect one column for bipartite networks. Both approaches are based on a well-designed stability certificate that connects the differential privacy requirement over all datasets and the probabilistic properties on regular datasets. Our contribution are as follows.

First, our NetPTR privatizes the empirical spectral embedding directly. NetPTR applies a stability-based release rule to the leading empirical eigenspace and then performs the usual row-normalization and \(K\)-means steps. We establish theoretical guarantee on its \((\varepsilon, \delta)\)-differential privacy. To our knowledge, this is the first estimator-specific edge-DP method for spectral community detection that directly controls the sensitivity of the spectral embedding and comes with statistical recovery guarantees.

Second, we develop new one-edge perturbation analysis for private spectral clustering. Classical perturbation theories assume arbitrary noise, but not tailored to the perturbation with only one edge. We establish an exact bound that controls the eigenspace perturbation both in spectral norm and in \(2 \to \infty\) norm under verifiable conditions involving degree scale, signal and noise eigenvalues, and row-wise incoherence. These quantities define a computable stability certificate \(\gamma_E\) and a local sensitivity level for noise calibration. Hence, this analysis is the key that connects differential privacy to spectral clustering accuracy.

Third, we establish consistency and rate-optimality of NetPTR under the degree-corrected stochastic blockmodel (DCSBM). The protection of privacy inevitably brings a loss in accuracy, and this accuracy loss must be discussed under model assumptions. Under a regular DCSBM, we find the misclustering rate of NetPTR, which decomposes into the usual non-private spectral clustering error and an additional privacy-induced term. Roughly speaking, when the privacy budget \(\varepsilon\) is larger than the reciprocal of average degree, NetPTR achieves weak consistency, and even strong consistency in the moderate sparse networks. We further establish the lower bound for all edge-DP estimators, where no edge-DP estimator can achieve strong consistency when \(\varepsilon\) is smaller than this scale. Hence, NetPTR is sharp up to logarithmic factors.

Fourth, we extend the construction to bipartite networks under column-node privacy. In this setting, the protected unit is a column of the adjacency matrix and the target is the community structure of the left-side nodes. Hence, the perturbation geometry is different from edge-DP for ordinary networks. We construct an eigengap-based stability certificate for the left spectral embedding. Based on this stability certificate, we propose Bi-NetPTR, prove \((\varepsilon, \delta)\)-column-node DP, and establish consistency; see Theorems [thm:BiDP]–[thm:BiOptimal]. To our knowledge, this is the first node-DP spectral community detection method with a corresponding statistical analysis for bipartite networks.

Finally, we evaluate our methods on synthetic and real networks. The simulations validate the predicted privacy-utility tradeoff under both DCSBM and Bi-DCSBM, including the effects of privacy budget, network size, degree scale, and the number of right-side nodes. The Flickr contact network and Senate roll-call analysis illustrate that NetPTR can retain interpretable community structure under the corresponding privacy notions.

1.2 Related Literature↩︎

Differential privacy for graph data is commonly studied under edge-level or node-level neighboring relations; see [8] and [9] for surveys. Existing work either releases private graph summaries, such as degree distributions and subgraph counts [10], [11], or privatizes the graph through randomized-response and edge-flipping mechanisms [12], [13]. For a privatized graph, any downstream analysis is private. However, this perturbation is calibrated to the graph representation rather than to a specific inferential target. [14] points out that such graph perturbation mechanism cannot outperform other mechanisms, but has a lower computation complexity. [15] establishes weak consistency of edge-flipped spectral clustering, which requires the degree scale to be at \(\sqrt{n}\). Related extensions include edge-flipping spectral clustering for well-clustered graphs [16], privacy-integrated graph clustering [7], [17] and personalized edge flipping [18]. More recently, [19], [20] investigate node-private community recovery. Research about bipartite networks are much less. [21] has studied the common-neighborhood estimation under edge-DP. Our method instead privatizes the empirical spectral embedding directly and provides theory for both edge-DP ordinary networks and column-node-DP bipartite networks, including sparse networks.

A standard DP release calibrates noise to global sensitivity [5], which can be conservative when an estimator is stable on typical datasets but unstable on rare inputs. Propose-Test-Release (PTR) avoids this worst-case calibration by privately testing whether the input is sufficiently far from instability before releasing a noisy statistic [22], [23]. Recent efficient PTR methods replace the exact distance-to-instability by a computable Lipschitz sub-distance [24]. In our setting, we use this efficient PTR template, but design it to adapt the network setting. The main task is to establish the perturbation results of empirical leading eigenspace, so that we can construct a computable stability certificate that satisfies the requirements of efficient PTR template.

Matrix Perturbation. Spectral community detection relies on eigenspace perturbation theory [25], [26]. Davis–Kahan bounds control subspace error through an eigengap [27], while entrywise and \(2\to\infty\) perturbation bounds give the row-wise control needed for exact label recovery [28], [29]. These results usually compare a random adjacency matrix with its population mean. Differential privacy requires a different comparison: two neighboring observed networks. For edge-DP, we analyze the one-edge perturbation of the empirical eigenspace and obtain spectral-norm and \(2\to\infty\) local sensitivity bounds. This calculation is what makes the stability certificate \(\gamma_E\) computable.

1.3 Organization and Notations↩︎

The remainder of the paper is organized as follows. Section 2 reviews spectral clustering under the network model and the efficient PTR template. Section 3 develops the edge-DP NetPTR procedure for ordinary networks, where the consistency and lower-bound guarantee are established in Section 4. Section 5 extends the method to bipartite networks under column-node privacy. Sections 6 and  7 present simulation and real-data studies. Proofs and additional numerical results are deferred to the supplementary material.

For an integer \(n\), write \([n]=\{1,\ldots,n\}\). For a matrix \(M\), let \(\lambda_k(M)\) denote its \(k\)th largest eigenvalue in magnitude for symmetric \(M\), and \(\|M\|\), \(\|M\|_F\), \(\|M\|_{\infty}\) and \(\|M\|_{2,\infty}\) its spectral, Frobenius, maximum row-sum, and \(2 \to \infty\) norms, respectively. We use \(A\sim_E A'\) for edge-adjacent ordinary networks and \(B\sim_N B'\) for column-node-adjacent bipartite networks. The notation \(c\) and \(C\) denotes positive constants whose values may change from line to line. We write \(a_n\lesssim b_n\) if \(a_n\le Cb_n\) for a constant \(C\), and \(a_n\asymp b_n\) if both \(a_n\lesssim b_n\) and \(b_n\lesssim a_n\) hold.

2 Spectral Community Detection and Efficient PTR↩︎

2.1 Network Model and Spectral Community Detection↩︎

We first introduce the network model and the non-private spectral community detection procedure that will be privatized in later sections. While our private procedure does not rely on specific network models, the consistency and optimality analysis require a model.

Let \(A\in\{0,1\}^{n\times n}\) be the adjacency matrix of an undirected graph on the node set \([n]\). We consider the degree-corrected stochastic block model (DCSBM) [30]. Under DCSBM, \(A\) has independent Bernoulli entries where \(A_{ij}\sim \mathrm{Bernoulli}(\Omega_{ij})\) for a population matrix \(\Omega\), with \(A_{ji}=A_{ij}\) and \(A_{ii}=0\). The population matrix takes the form \(\Omega=\Theta\Pi P\Pi^\top\Theta\), where \(\Theta=\mathrm{diag}(\theta_1,\ldots,\theta_n)\) contains node-specific degree parameters, \(\Pi\in\{0,1\}^{n\times K}\) is the membership matrix, and \(P\in\mathbb{R}^{K\times K}\) is the block connectivity matrix. Let \(\ell(i)\in[K]\) denote the community label of node \(i\), then \(\Pi_{ik}=1\{\ell(i)=k\}\). The statistical target is the label vector \(\ell=(\ell(1),\ldots,\ell(n))\) with \(K\) being known.

The eigenspace formed by \(K\) leading eigenvectors is used to recover \(\ell\). Let \(\Xi_K\in\mathbb{R}^{n\times K}\) collect the eigenvectors of the population matrix \(\Omega\) associated with its \(K\) largest eigenvalues in magnitude. In [2], [3], [26], it is shown that there exists a nonsingular matrix \(H \in \reals^{K \times K}\), so that for node \(i\) with \(\ell(i) = k\), \(e_i^\top \Xi_K=\theta_i e_k^\top H\). Spectral community detection algorithms have been proposed based on this observation in the existing literature, and we consider Algorithm 1 in [26] for privacy analysis.

2.2 Efficient Propose-Test-Release Framework↩︎

We first recall the definition of differential privacy. Let \(\mathcal{A}\) be a data space with an adjacency relation \(\sim\). A randomized estimator \(\hat{\theta}:\mathcal{A}\to\mathcal{O}\) is \((\varepsilon,\delta)\)-differentially private with respect to \(\sim\) if, for all \(A,A'\in\mathcal{A}\) satisfying \(A\sim A'\) and all measurable sets \(S\subseteq\mathcal{O}\), \[P(\hat{\theta}(A)\in S) \le e^\varepsilon P(\hat{\theta}(A')\in S)+\delta .\] Here, \(\varepsilon\) and \(\delta\) measures the protection on privacy and the adjacency relation specifies the protected unit.

Propose-test-release (PTR) is designed for estimators with an excessive global sensitivity but a small local sensitivity on a regular set in the data space [22]. Given a target sensitivity level \(\alpha\), PTR first identifies the datasets \(\mathcal{G}_{\alpha}\) on which the estimator is locally \(\alpha\)-stable. It then privately tests on the distance from \(A\) to the unstable region, the complement \(\mathcal{G}_{\alpha}^c\). When the test is passed, PTR releases the estimator with a noise calibrated by the local sensitivity \(\alpha\); otherwise a data-independent response \(\perp\) is released. Hence, the noise level is reduced to the local sensivity \(\alpha\).

In the test step of PTR, the exact distance from the observed dataset \(A\) to the unstable region \(\mathcal{G}_{\alpha}^c\) is required. For spectral estimators, \(\mathcal{G}_{\alpha}^c\) is nonconvex and this distance calculation is generally intractable. Efficient PTR (ePTR) replaces the exact distance by a computable Lipschitz sub-distance [24], which can be regarded as the stability certificate of \(A\). Its template is in Algorithm 2 and the theoretical guarantee is in Theorem [thm:fPTR].

Theorem [thm:fPTR] shows that ePTR has a noise calibrated to the local sensitivity \(\alpha\), given that the stability certificate \(\gamma\) is well-defined. For spectral community detection, the derivation of \(\alpha\) and \(\gamma\) is nontrivial. We need \(2\to\infty\) perturbation control on the empirical eigenspace \(\widehat\Xi_K\) under a one-edge change of the adjacency matrix, which is a non-standard local perturbation analysis.

3 Edge-Private Spectral Community Detection↩︎

3.1 One-edge Perturbation and Stability Certificate↩︎

We first define the adjacency relationship for edge-DP, and then derive the global sensitivity and local sensitivity of the empirical eigenspace \(\Xihat_K(A)\) in Algorithm 1. For two symmetric adjacency matrices \(A,A'\in\{0,1\}^{n\times n}\), define \[d_E(A,A')=\sum_{1\le i<j\le n}1\{A_{ij}\neq A'_{ij}\}.\] We write \(A\sim_E A'\) if \(d_E(A,A')=1\). If an estimator \(\tilde{\theta}\) satisfies that for any Borel set \(\mathcal{B}\), \(P(\tilde{\theta}(A) \in \mathcal{B}) \leq e^{\varepsilon}P(\tilde{\theta}(A') \in \mathcal{B}) + \delta\) when \(A \sim_E A'\), then \(\tilde{\theta}\) is called an \((\varepsilon, \delta)\)-edge-differentially private (edge-DP) estimator.

Now we examine the perturbation in the leading eigenvector matrix. Let \(\Xihat_K(A) \in \reals^{n \times K}\) and \(\Xihat_K(A') \in \reals^{n \times K}\) be the matrices consisting of the leading \(K\) eigenvectors of \(A\) and \(A'\), correspondingly. The following proposition bounds both the spectral norm and the \(2\to\infty\) norm under one-edge perturbation are controlled up to a rotation, given that \(A\) is regular.

Proposition [pro:detailedlinifty] identifies a region on which \(\hat{\Xi}_K\) is locally stable under one-edge perturbations. The required conditions have standard spectral interpretations: the maximum degree scale is controlled, the \(K\)th signal eigenvalue is separated from the noise eigenvalue \(\lambda_{K+1}(A)\), and the leading empirical eigenspace is row-wise incoherent. The parameter \(\theta_0\) denotes the network sparsity. These conditions motivate the regular set \[\begin{align} \mathcal{G}_E=\Big\{A \in \{0, 1\}^{n \times n}:\;& \|A\|_{\infty}\le (1+a_0)n\theta_0^2,\quad \lambda_K(A)\ge a_0n\theta_0^2+3\sqrt 2,\\ &\lambda_{K+1}(A)\le \frac{4}{5} a_0n\theta_0^2,\quad \|\Xihat_K(A)\|_{2,\infty}\le \frac{A_0}{\sqrt n} \Big\}. \end{align}\] On this regular set \(\mathcal{G}_E \subset \mathcal{A}\), the local sensitivity level is \(\alpha_E = \sqrt K\Bigl( \frac{5\sqrt 2 A_0}{a_0\theta_0^2 n\sqrt n} + \frac{50A_0^2}{a_0^2\theta_0^4 n^3} \Bigr)\) in Proposition [pro:detailedlinifty]. This bound improves the classical Davis-Kahan bound by an \(1/\sqrt{n}\) order. Furthermore, we also establish the sensitivity level in terms of \(2\to\infty\) norm, which is required in strong consistency.

The definition of \(\mathcal{G}_E\) sheds light on the definition of the stability certificate \(\gamma_E(A)\). Here, \(\gamma_E(A)\) evaluates the stability of a dataset \(A\), where a larger \(\gamma_E(A)\) indicates that \(A\) is more stable, and \(\gamma_E(A) > 0\) indicates that \(A \in \mathcal{G}_E\). We define \(\gamma_E(A)\) via similar terms as \(\mathcal{G}_E\) and re-scale these terms to guarantee that \(\gamma_E(A)\) is 1-Lipschitz.

Each component of \(\gamma_E\) is computable from \(A\). The degree and eigenvalue terms are Lipschitz under one-edge changes by elementary norm bounds and Weyl’s inequality. The incoherence term is controlled by the \(2\to\infty\) perturbation bound in Proposition [pro:detailedlinifty]. Hence \(\gamma_E\) is a valid sub-distance for \(\mathcal{G}_E\), and \(\{\gamma_E(A)>0\}\subset \mathcal{G}_E\).

3.2 NetPTR for edge-private spectral clustering↩︎

We now propose our NetPTR approach, which proposes a private spectral community labels on social networks. We first release a private spectral space \(\tilde{\Xi}_K(A)\) based on the stability certificate \(\gamma\). It will be a perturbed estimate with noise calibrated by the local sensitivity level \(\alpha_E\) in Proposition [pro:detailedlinifty] for large \(\gamma_E(A)\); otherwise it is a private release with \(\gamma\)-dependent probability to be a data-independent vector. Then we normalize the rows and apply \(k\)-means for the labels by Algorithm 1. The theoretical guarantee on privacy is in Theorem 1.

It remains to discuss the choice of the density-scale parameter \(\theta_0\). Algorithm 3 uses \(\theta_0\) as a density-scale parameter in the stability certificate. In some applications, \(\theta_0\) may be chosen from public information or domain knowledge. When this is not available, we propose a private estimate from the maximum degree. Since \(\|A\|_\infty\) changes by at most one under edge adjacency, the Laplace mechanism gives \[\widetilde{\theta}_0(A) = \left[ \frac{\|A\|_\infty+\eta}{n} \right]_+^{1/2}, \qquad \eta\sim \mathrm{Lap}(1/\varepsilon_1),\] as an \((\varepsilon_1,0)\)-DP estimate of the network density scale. Running Algorithm 3 with \(\widetilde{\theta}_0(A)\) in place of \(\theta_0\) then gives the following composition guarantee.

4 Rate Optimality of NetPTR under the DCSBM↩︎

4.1 Upper Bound and Consistency↩︎

We now study the error bound of NetPTR. The privacy guarantee in Theorem 1 is deterministic and holds for every input graph, whereas error analysis requires a distributional model. We consider the degree-corrected stochastic blockmodel (DCSBM) in the following analysis. We are interested in the statistical error in the non-private estimator, and the additional error introduced to protect privacy. The goal is to minimize the additional error while the privacy is still well-protected.

We consider a regular DCSBM class, which is commonly used in social network literature [2], [3], [30], [31]. The communities are non-vanishing, degree parameters comparable to a common scale \(\theta_0\), and the block connectivity matrix full rank with bounded spectrum. These conditions ensure that the population eigenspace identifies the community structure and that the non-private estimator enjoys statistical consistency.

For fixed constants \(C_0>0\) and \(\rho\in(0,1]\), define the regular population class \[\calM_{\theta_0,C_0,\rho} = \Bigl\{ \Omega=\Theta \Pi P \Pi\ic \Theta: \Pi\in \mathcal{L}_{\rho},\; \frac{\theta_0}{C_0}<\theta_i<C_0\theta_0,C_0^{-1} < \lambda_K(P) < \lambda_1(P) < C_0, \|\Omega\|_\infty\le n\theta_0^2 \Bigr\}.\] \(\calM_{\theta_0,C_0,\rho}\) contains the population matrices with nonvanishing communities and node-specific degree parameters on a common scale. Hence, it naturally guarantees that the observed network \(A\) falls into \(\mathcal{G}_E\) with high probability. It is not surprising. To guarantee the consistency of spectral community detection methods, it is indirectly required that the dataset has a stable eigenspace with high probability.

The following theorem gives the (strong) consistency of NetPTR under this class.

Theorem [thm:optimal] gives both weak and strong consistency guarantees. The weak consistency is guaranteed when the misclustering rate goes to 0. The strong consistency is guaranteed under the additional signal condition \(\theta_0^2\sqrt n\ge 1/a_0\), i.e. the average degree is at \(\sqrt{n}\). The edge-flipping method needs a degree scale to be linearly dependent on \(n\) for strong consistency, which is much stronger [15].

The two terms in the upper bound have distinct origins. The first term is the non-private spectral clustering error under the DCSBM, which goes to 0 when the degree scale \(n\theta_0^2 \to \infty\). The second term is the additional error induced by the Gaussian perturbation in NetPTR. It decreases as the privacy budget \(\varepsilon\) increases and as the degree scale increases. When the privacy budget \(\varepsilon \gtrsim \frac{\log n}{n\theta_0^2}\), then the consistency is guaranteed. Thus the theorem gives an explicit privacy–accuracy decomposition.

The same accuracy conclusion continues to hold when the density-scale parameter \(\theta_0\) is estimated privately. The next corollary combines the private estimation of \(\theta_0\) with the NetPTR release through composition.

4.2 Lower Bound↩︎

We next establish the lower bound for the privacy budget \(\varepsilon\) to achieve consistency for any private estimators under DCSBM. The following theorem demonstrates that, even when the degree scale is large and the non-private estimator is consistent, the privacy budget \(\varepsilon \lesssim 1/(n\theta_0^2)\) will cause failure in strong consistency for any private estimators.

The proof constructs two DCSBM populations that differ only in the label of one fixed node. Under a natural coupling, the sampled networks differ only through edges incident to that node, and their edge distance is of order \(n\theta_0^2\) with high probability. Group privacy then prevents any \((\varepsilon,\delta)\)-edge DP algorithm with \(\varepsilon \lesssim 1/(n\theta_0^2)\) from distinguishing the two labels with probability tending to one.

Theorem [thm:optimal] shows that our NetPTR approach has strong consistency when \(\varepsilon \geq \log(n)/(n\theta_0^2)\). It matches the rate \(\varepsilon < 1/(4n\theta_0^2)\) in Theorem [thm:lowerbound], up to a logarithmic factor. Hence our NetPTR approach is rate-optimal in privacy budget.

5 Column-Node-Private Community Detection on Bipartite Networks↩︎

5.1 Bipartite Spectral Clustering and Column-Node Privacy↩︎

We next extend NetPTR to bipartite networks under a stronger privacy requirement. Let \(B\in\{0,1\}^{n\times m}\) record interactions between subjects or users \(U=[n]\) and items, bills, or other units \(V=[m]\). The goal is to cluster the nodes in \(U\) from their response across \(V\). We consider column-node privacy, which protects the full response profile associated with one item in \(V\), rather than protecting only one edge as the ordinary networks. This stronger notion is more practical. For example, a particular question may reveal how all users responded to it. We therefore seek to release the community labels of \(U\) while preventing inference about any item-level response profile.

For bipartite community detection on \(U\), the spectral approach is to exploit the left singular vectors of \(B\), i.e., the leading eigenvectors of \(m^{-1}BB\ic\) in magnitude, denoted as \(\hat{\Xi}_K\). The non-private spectral clustering algorithm applies row normalization and \(K\)-means to \(\hat{\Xi}_K\); see Algorithm 4.

We then formalize the column-node privacy. Write \(B=[B_1,\ldots,B_m]\), where \(B_j\in\{0,1\}^n\) is the column corresponding to node \(j\in V\).

We call an estimator \(\tilde{\theta}(B)\) as \((\varepsilon, \delta)\)-node DP, if for any Borel set \(\mathcal{B}\), \(P(\tilde{\theta}(B) \in \mathcal{B}) \leq e^{\varepsilon}P(\tilde{\theta}(B') \in \mathcal{B}) + \delta\). It requires the output distribution to be stable when one column of \(B\) is replaced.

5.2 Bi-NetPTR↩︎

We now construct the column-node-private version of NetPTR. It still requires perturbation analysis and then a proposal of stability certificate. Let \(Gap(M)=\lambda_K(M)-\lambda_{K+1}(M)\) for a positive semidefinite matrix \(M\). By Davis-Kahan theorem, the perturbation in \(\Xihat_K(B)\) is related to the eigengap of \(BB\ic\). Hence, we use an eigengap certificate.

Suppose \(\theta_0\) denote the universal heterogeneity scale for all left and right side nodes, which is similar as \(\theta_0\) in DCSBM. Then \(Gap(BB\ic)\) is at the order of \(mn\theta_0^4\) with high probability. We consider the sensitivity level on these networks. Define the good set \[\mathcal{G}_I = \left\{ B:Gap(BB\ic)>a_0\theta_0^4 nm \right\},\] and the sub-distance, i.e., stability certificate, is defined as \[\gamma_I(B) = \frac{1}{2n} \left\{ Gap(BB\ic)-a_0\theta_0^4nm \right\}_+ = \frac{m}{2n} \left\{ Gap\left(\frac{1}{m} BB\ic\right)-a_0\theta_0^4 n \right\}_+.\] Here, \(\gamma_I\) has an normalization parameter \((2n)^{-1}\), to ensure it is 1-Lipschitz under column-node adjacency. When \(\gamma_I(B)>0\), the eigengap of \(m^{-1}BB\ic\) is large enough for Davis–Kahan theorem to control the local sensitivity of \(\Xihat_K(B)\). The corresponding local sensitivity level is \(\alpha_I=\frac{4\sqrt{2}}{a_0\theta_0^4m}\), with rigorous derivation in Section 5.3.

Base on the stability certificate and perturbation analysis, we propose Bi-NetPTR as Algorithm 5. For a network \(B\) with a large eigengap, we release a perturbed eigenspace \(\tilde{\Xi}_K(B)\), where the noise is calibrated by the local sensitivity level \(\alpha_I\). When the network \(B\) has a small eigengap, we release a data-independent output. The privacy guarantee is demonstrated in Theorem [thm:BiDP].

Algorithm 5 uses \(\theta_0\) as a density-scale input in the stability certificate. In some applications, this parameter can be supplied from public information or domain knowledge. Otherwise, it can be estimated privately. Since \(\|B\|_\infty\) changes by at most one under column-node adjacency, the Laplace mechanism gives \[\label{eqn:thetatilde95bi} \thetatilde_0(B) = \left[ \frac{\|B\|_\infty}{m} + \frac{\mathrm{Lap}(1/\varepsilon_1)}{m} \right]_+^{1/2},\tag{2}\] as an \((\varepsilon_1,0)\)-DP estimate. Applying Algorithm 5 with \(\thetatilde_0(B)\) gives an \((\varepsilon+\varepsilon_1,\delta)\) column-node-DP estimator by composition.

5.3 Consistency under the Bi-DCSBM↩︎

We now introduce the bipartite degree-corrected stochastic block model (Bi-DCSBM) for accuracy analysis. Conditional on a population matrix \(\Omega\in[0,1]^{n\times m}\), the entries of \(B\) follow \(B_{ij}\sim \mathrm{Bernoulli}(\Omega_{ij})\) independently, \(i\in[n]\), \(j\in[m]\). \(\Omega\) takes the form \[\label{eqn:bisbm} \Omega=\Theta\Pi_n P_B\Pi_m\ic\Phi .\tag{3}\] Here \(\Theta=\mathrm{diag}(\theta_1,\ldots,\theta_n)\) and \(\Phi=\mathrm{diag}(\phi_1,\ldots,\phi_m)\) contain degree heterogeneity parameters on the left and right sides, \(\Pi_n\in\{0,1\}^{n\times K}\) and \(\Pi_m\in\{0,1\}^{m\times J}\) are membership matrices, and \(P_B\in\reals^{K\times J}\) is the block connectivity matrix. It is connected to the ordinary networks through the population Gram matrix: \[\frac{1}{m} \E[B]\E[B]\ic = \Theta\Pi_n P\Pi_n\ic\Theta, \qquad P:=\frac{1}{m} P_B\Pi_m\ic\Phi^2\Pi_m P_B\ic .\] Thus the left-side spectral problem has the same degree-corrected form as in the ordinary-network case, with an induced block matrix \(P\). Under the regularity conditions below, this induced matrix has a nondegenerate \(K\)-dimensional signal.

Define the regular label class so that every community on both sides is non-vanishing. \[\mathcal{L}_\rho^B := \left\{ (\Pi_n,\Pi_m): \Pi_n\mathbf{1}_K=\mathbf{1}_n,\;\Pi_m\mathbf{1}_J=\mathbf{1}_m,\;\mathbf{1}_n\ic\Pi_n e_k\ge \rho n,\;\mathbf{1}_m\ic\Pi_m e_j\ge \rho m \right\}.\] For fixed constants \(C_0>0\) and \(\rho\in(0,1]\), define \[\begin{align} \calM^B_{\theta_0,C_0,\rho} = \Bigl\{ \Omega=\Theta\Pi_n P_B\Pi_m\ic\Phi:\;& (\Pi_n,\Pi_m)\in\mathcal{L}_\rho^B,\;C_0^{-1}\theta_0<\theta_i,\phi_j\le C_0\theta_0,\\ & C_0>\sigma_1(P_B)\ge \sigma_K(P_B)>C_0^{-1},\;\|\Omega\|_\infty\le m\theta_0^2 \Bigr\}. \end{align}\] Here \(\sigma_k(P_B)\) denotes the \(k\)th singular value of \(P_B\), which ensures the induced signal is full rank. The degree parameters on both sides are on the common scale \(\theta_0\).

The first term in Theorem [thm:BiOptimal] is the non-private spectral error for estimating the left communities from the bipartite network. The second term is the additional error caused by column-node privacy. The bound decreases as \(m\) increases, reflecting that the matrix \(m^{-1}BB\ic\) becomes more stable when more right-side profiles are observed. The next result records that the same conclusion holds when \(\theta_0\) is privately estimated by 2 .

6 Simulation↩︎

6.1 Edge-Private Community Detection↩︎

We first evaluate the edge-private NetPTR procedure under the DCSBM. In each experiment, we fix \(K=2\) and assign exactly \(n/2\) nodes to each community. The block connectivity matrix \(P \in \reals^{2 \times 2}\) has \(p_{in}\) on diagonals and \(p_{out}\) on diagonals. The population matrix \(\Omega=\Theta\Pi P\Pi^\top\Theta\), where \(\Theta\) and \(\Pi\) are randomly generated from a given distribution in each repetition. We then sample \(A\) by \(A_{ij}\sim{\rm Bernoulli}(\Omega_{ij})\) independently for \(i<j\). It is symmetrized to obtain an undirected adjacency matrix.

We consider two scenarios. The first is a regular scenario with \((p_{\rm in},p_{\rm out})=(0.4,0.1)\) and \(\theta_i\sim{\rm Unif}(0.1,0.5)\). The second is a heterogeneous scenario with \((p_{\rm in},p_{\rm out})=(0.9,0.3)\), where \(\theta_i\sim{\rm Unif}(0.1,0.5)\) with probability \(0.6\) and \(\theta_i\sim{\rm Unif}(0.01,0.05)\) with probability \(0.4\). Hence, it contains a large fraction of low-degree nodes, which is more challenging for private spectral clustering. We examine the accuracy of NetPTR in the two scenarios versus sample size \(n\), privacy budget \(\varepsilon\), and private \(\theta_0\). The accuracy is evaluated by the Hamming distance between the estimated label and ground truth.

Sample size and privacy budget. We first study NetPTR as a standalone private clustering method. We vary the sample size \(n\in\{5000,10000,15000,\cdots,50000\}\), the privacy budget \(\varepsilon\in\{0.5,0.8,1.0\}\), and fix \(\delta=0.01\). We compare two versions of Algorithm 3: a non-private estimate \(\hat{\theta}_0\), and a fully private version using \(\tilde{\theta}_0\) with \(\varepsilon_1=0.2\). The non-private community detection algorithm is included as a comparison. Each configuration is repeated 50 times.

Figure 6 summarizes the mean community detection error rate versus \(n\) for each \(\varepsilon\). To protect the privacy, NetPTR suffers a larger clustering error rate than the non-private algorithm. This error rate decreases as the sample size increases or the privacy budget increases. In the regular scenario, NetPTR achieves an error rate at 0 at moderate sample size \(n \geq 20,000\). With private \(\tilde{\theta}_0\), the error rate of NetPTR is slightly larger, but still achieves 0 when \(n \geq 30,000\). In the heterogeneous scenario with extreme sparsity, even the non-private method has a larger clustering erro rate. NetPTR introduces a mild additional error rate at around \(0.1\) in this scenario. It indicates the robustness of NetPTR.

Comparison with edge flipping. We compare our NetPTR with the classical edge-flipping baseline (EdgeFlip, implemented following the procedure in [14]). Fix \(n=20000\) and vary the privacy budget \(\log_2(\varepsilon) \in \{-1,-0.75,\cdots,0.75,1\}\) and \(\delta = 0.01\). For each \(\varepsilon\), we run NetPTR with known \(\theta_0\) \((\varepsilon_0 = \varepsilon, \varepsilon_1 = 0)\) and a private estimate \(\tilde{\theta}_0\) \((\varepsilon_0 = \varepsilon-0.2, \varepsilon_1 = 0.2)\) respectively, as well as EdgeFlip. We summarize the mean clustering error over 50 independent replications in Figure 7. It can be seen that NetPTR, whether with non-private \(\hat{\theta}_0\) or private \(\tilde{\theta}_0\), improves substantially faster as the privacy budget \(\varepsilon\) increases in both scenarios.

Network Sparsity. We examine the privacy-utility behavior with varying \(\theta_0\) levels. Let \(\theta_i\sim \mathrm{Unif}(a,a + 0.4)\) for the regular scenario and \(\theta_i\sim 0.6 \mathrm{Unif}(a,a + 0.3) + 0.4 \mathrm{Unif}(0.1a,0.1a + 0.03)\) for the scenario with extreme sparsity. The parameter \(\theta_0 = \sqrt{\|\Omega\|_{\infty}/n}\) is decided by \(a\). We vary \(a\) to figure out its values that \(\theta_0\) ranges from .10 to .50 by a step size of \(.05\) in the regular setting, and \(\theta_0\) ranges from .175 to .550 by a step size of \(.0625\) for the scenario with extreme sparsity. Fix \(n=20000\), \(\varepsilon = 0.8\) and \(\delta = 0.01\).

The mean clustering errors over 50 repetitions are summarized in Figure 8. For both scenarios, the non-private spectral clustering baseline is nearly exact across varying \(\theta_0\), so the separation between curves mainly reflects privacy-induced perturbations. As \(\theta_0\) increases, the performance of both private mechanisms improves. NetPTR improves more rapidly and achieves near-exact recovery at moderate \(\theta_0\), whereas EdgeFlip remains at an error rate \(0.2\) in the scenario with extreme sparsity with large \(\theta_0\). It is consistent with Theorem [thm:optimal], where NetPTR has an error bound with respect to the network density, but EdgeFlip suffers in this degree heterogeneous setting.

6.2 Bipartite-network experiments under Bi-DCSBM↩︎

We evaluate Bi-NetPTR in Section 5. Consider \(n = 800\) left nodes and \(m = 8000\) right nodes. Fix \(K = 2\) left-communities and \(J = 2\) right-communities, and assign exactly \(n/2\) left nodes and \(m/2\) right nodes to each community. Generate the degree parameters independently as \(\theta_i, \phi_j \sim \mathrm{Unif}(0.7,1.0)\). The adjacency matrix follows that \(B_{ij}\sim \mathrm{Bernoulli}(\theta_i \phi_j p_{\ell_1(i), \ell_2(j)})\), where \(p_{k,l} = 0.7*I\{k = l\} + 0.1*\{k \neq l\}\). For each generated \(B\), we apply the non-private bipartite spectral clustering method as Algorithm 4, as well as the Bi-NetPTR method with \(\varepsilon\) and \(\delta=0.01\).

Privacy budget. We first study how the clustering accuracy changes with the privacy budget \(\varepsilon\). We vary \(\varepsilon \in \{0.5,1.0,2.0,4.0\},\) and consider three privacy-budget splits for Bi-NetPTR, \(\varepsilon_1\in\{0,0.1,0.2\},\) where \(\varepsilon_1>0\) corresponds to using a private estimate of \(\theta_0\).

The upper panel of Table 1 reports the mean clustering error, standard deviation, and empirical release frequency among 50 repetitions. The non-private method achieves zero error in all repetitions and is omitted from the table. As \(\varepsilon\) increases, the clustering error decreases to 0 no matter what split we use. For a small privacy budget \(\varepsilon = 0.5\), allocating part of the budget to \(\theta_0\) leads to a lower release frequency and hence larger error. When \(\varepsilon \geq 1.0\), the release probability increases to 1 quickly. Hence, the private estimation of \(\theta_0\) is practically feasible.

Varying the number of right-side nodes. We fix \(n=800\) and \(\varepsilon=3.0\), and vary the number of right-side nodes over \(m\in\{1000,1500,2000,3000,\) \(4000,5000,6000,7000\}.\) We consider \(\varepsilon_1\in\{0,0.1,0.2\}\). The results over 50 repetitions are recorded in the lower panel of Table 1.

With a larger \(m\), the perturbation of one column has a smaller effect on the eigengap of \(m^{-1}BB^\top\), and all Bi-NetPTR methods improve. Using a private \(\tilde{\theta}_0\), the release probability is small when \(m \leq 2000\), and it turns to one when \(m \geq 3000\). Overall, these results support the practical effectiveness of the Bi-NetPTR procedure.

7 Real Data Analysis↩︎

7.1 Flickr Contact Network↩︎

The Flickr network comes from the Social Computing Data Repository (https://datasets.syr.edu/Flickr/), where each node represents a user and each edge represents the friendship between the two users. In such social networks, a user may wish to keep certain connections private, for example when the connection is with a controversial or reputationally sensitive user. This makes the dataset a natural example for edge-private community detection. We remove the nodes with degree smaller than \(100\). In the processed network, there are \(n=26082\) nodes and \(4416654\) undirected edges.

We apply NetPTR and EdgeFlip on this network for \(\varepsilon \in \{2.0, 2.5, 3.0, 3.5, 4.0\}\) and \(\delta = 0.01\) for 20 independent repetitions. To each repetition, we randomly choose \(10\%\) nodes for private estimate. For NetPTR, we consider private \(\tilde{\theta}_0\) with \(\varepsilon_1 = 0.2\) and \(\varepsilon_1 = 0.5\). The parameters are chosen as \(a_0 = .1\) and \(A_0 = 50\).

We assess utility by comparing each private clustering result with the non-private spectral clustering partition using the adjusted Rand index (ARI). A higher ARI indicates a better alignment between the two estimates. Table 2 reports the mean ARI values across 20 replications. As expected, the ARI of both methods improves as the privacy budget \(\varepsilon\) increases. EdgeFlip and NetPTR have a similar performance for small \(\varepsilon = 2.0\), but NetPTR clearly outperforms EdgeFlip when \(\varepsilon \ge 2.5\), where the gap widens steadily as \(\varepsilon\) increases. In addition, EdgeFlip is computationally less appealing because it must explicitly perturb \({n \choose 2}\) possible edges, while NetPTR adds noise to \(n \times K\) entries. Overall, NetPTR protects the privacy, outperforms other methods, and is computationally efficient.

4pt

7.2 Senate Roll-call Voting↩︎

The roll-call voting records from the 109th U.S. Senate are represented as a bipartite network connecting senators to roll-call votes [32], [33]. After preprocessing, the data contains \(n=102\) legislators as left-side nodes and \(m=406\) roll calls as right-side nodes. Each edge indicates that the legislator votes “yes" to the corresponding roll call. Each legislator is encoded with their party, which is the ground truth. The dataset and processing code can be found at https://tinyurl.com/NetPTR-SC.

We apply non-private and private spectral clustering with \(K=2\) to the legislators. The private estimates include EdgeFlip, Bi-NetPTR with \(\varepsilon_1=0\), and Bi-NetPTR with \(\varepsilon_1=0.5\). The edge-flipping mechanism was designed for edge-DP, and here we extend it into the node-level privacy via \(\varepsilon_{edge} = \varepsilon/m\). The left panel in Figure 9 reports the ARI between the private outputs and the non-private benchmark versus the privacy budget \(\varepsilon\), where a larger ARI indicates a higher agreement. As \(\varepsilon\) increases, both Bi-NetPTR variants have larger ARI scores, but EdgeFlip remains at 0 since \(\varepsilon_{edge}\) remains large even at moderate \(\varepsilon\). This difference explicitly explains the difficulty in node-level privacy. It suggests to consider a medium privacy regime.

At \(\varepsilon = 8\), the right panel in Figure 9 shows the party composition within each recovered cluster for the non-private method and for one replicate of Bi-NetPTR with \(\varepsilon_1=0.5\). The non-private method exhibits an almost perfect partition between the Democrats and Republicans, where the accuracy is \(0.98\). The private estimate, Bi-NetPTR, largely preserves this structure with a better privacy protection, at an reduced accuracy of \(0.95\) for Democrats, but the same accuracy for Republicans. Therefore, Bi-NetPTR still captures the structural information with effective privacy protection.

To understand how privacy protection manifests in this setting, we consider two test statistics \(t_1\) and \(t_2\). Let \(t_1(j)\) be the two-sample proportion \(z\)-statistic on the yes-rate for \(j\)-th roll call between the overall Republican and Democratic, which follows standard normal distribution under null hypothesis. For \(t_2(j)\), we again compare the yes-rates, but between the Republican legislators in Cluster 2 and the other Democrats. The histograms of \(t_1\) and \(t_2\) across roll-calls are summarized in Figure 10. It can be found that \(t_1\) exhibits a bimodal pattern, reflecting strong party distinction on many roll calls, whereas the \(t_2\) values are concentrated near 0, indicating weak separation between Republican legislators assigned to the Democratic-dominated cluster and the Democratic legislators themselves. This pattern suggests that the privacy protection mainly affects less polarized Republicans, whose voting records depart more often from the Republican majority. By contrast, highly polarized legislators with consistently party-line voting records remain in the Republican-dominated cluster. In a politically polarized environment, the response profile to a single vote may itself be sensitive, because it reveals how the population divides on a contested issue. Bi-NetPTR protects this full roll-call profile while still allowing the release of aggregate community structure.

Supplementary Materials:

Theoretical proofs of the main theorems and propositions, and additional numerical results on the simulated data and real data. (pdf file)

References↩︎

---

1. The authors gratefully acknowledge Singapore MOE grant Tier-1-A-8001451-00-00 and NUS Research Scholarship (IRP).↩︎