A Differentially Private Clustering Algorithm for Well-Clustered Graphs

We thank you for your reviews and address your concerns as follows. Q1: a). DP is not formally defined before the statement of theorem 1. b). The notation for $G_1 \Delta G_2$ is never defined. c). The trade-off between the utility and the $(\epsilon,\delta)$-DP is not clear in the statement. A1: We will incorporate your suggestions in the revised version. For example, we will add a pointer to the definition of DP before Theorem 1. The notion of $C_1\triangle C_2=(C_1\cup C_2)\setminus (C_1\cap C_2)$ is the symmetric difference between the sets $C_1$ and $C_2$. We will add a remark on the bound for the general instances and add a corresponding pointer to Lemma 4.3. Q2: The notion of $(\kappa, D_{1}, D_{2})$-strongly convex is not defined in the preliminary. A2: We have given the definition in Definition C.2, which is included in the appendix due to space constraints. We will add a pointer to the definition in the main text. Q3: I would still suggest the authors spend more passages to properly motivate the study of the clustering of well-clustered graphs. A3: Thanks for the suggestion. We will add some motivations or examples as follows. Consider any social network (Facebook, LinkedIn) that is defined by all the users in Europe. Intuitively, all the users from the same country will form a large cluster, and the whole graph is a good candidate for a well-clustered graph (and the linkage information is naturally private). One type of graph that often appears in downstream applications like recommendation or abuse detection applications is bipartite graphs (often these are social graphs). For example, such a graph may be defined on customers and products, and edges indicate that a customer purchased a product. Good clusters in these graphs contain nodes from both sides, but vanilla SBM models cannot generate these bipartite graphs with high probability. Studying a clustering property of graphs instead of a generative model allows us to overcome these shortcomings. Q4: Given the fact that the algorithm needs to run SDP, it’s unlikely that the algorithm can be scaled to modern social networks, which are the best candidates for well-clustered properties. Purely combinatorial algorithms would be much more helpful on this front. A4: We agree that it will be useful to have purely combinatorial algorithms, but currently we do not know how to obtain such algorithms with competitive privacy guarantee. Q5: Defining balance with volume seems to be a strong notion since it rules out the case when the clusters have comparable sizes but different densities. In contrast, I believe setting of CCDEIST [Neurips’23] only requires the vertices in two clusters to be balanced. A5: For graphs with varying degrees, it is much more convenient or natural to use volume to measure the importance of a vertex set $C$, which is roughly the number of all involved edges incident to $C$. This has already been discussed in the influential paper by Kannan, Vempala, and Vetta ("On clusterings: Good, bad and spectral." Journal of the ACM 2004), who motivated to use ''conductance'' to measure the quality of a cluster, instead of using the ''expansion''. The former is defined to be the ratio between the number of crossing edges and the *volume*, while the latter is the ratio between the number of crossing edges and the *size*. This leads to the use of volume to measure the importance of vertex sets in studying graph clustering. On the other hand, note that for graphs in which all the vertices have roughly the same degrees, it is almost the same to use the volume and sizes to measure the importance of a set or measure the balance. Under the assumptions of the SBM in CCDEIST[Neurips'23], the degrees of all vertices are roughly the same with high probability and their degrees cannot vary too much. Our algorithm deals with non-regular graphs, so adopting volume balance would be more appropriate. Q6: Can you report the runtime of your experiments and the hardware for your experiments? I want to get a sense of how far this algorithm is from being implementable in the real world and in the industry. A6: The experiments were run on a single Google Cloud n2-standard-128 instance. The CPU time (single core running time) for one run was about 2 minutes. For the experiments, we have 100 runs per input graph, times 10 input graphs, times 6 SBM parameterizations, times 2 algorithms, i.e., 12,000 runs. Q7: Your lower bound is for pure DP, can you get any result for pure $\epsilon$-DP upper bound with your technique? In particular, since you have a bound for the $\ell_1$ sensitivity of $f$, can you use Laplace mechanism to obtain a pure DP result? A7: Our current approach cannot get any result for pure $\epsilon$-DP, as we can only guarantee a good SDP solution with small $\ell_2$ sensitivity, due to the use of strong convexity of the regularized SDP. For $\epsilon$-DP, one always needs to have a non-trivial $\ell_1$-sensitivity bound.

We thank you for your reviews and address your questions as follows. Q1: One thing I’m not sure: does the balance parameter c also appear in the bound of Peng et al. 2015? This is not clearly discussed in your paper, and I think that this is very important. A1: Peng et al. did not explicitly specify the need for balance. Thank you for pointing this out, and we will incorporate these discussions. Q2: Whether (eps, delta)-DP is necessary is not justified; the upper bound is (eps, delta)-DP and the lower bound is about eps-DP. A2: Our Theorem 2 essentially indicates that when the classification error is $o(1)$, there is no pure-DP algorithm for this problem with a constant $\epsilon$. We will provide further clarification on this in the paper. On the other hand, our algorithmic result Theorem 1 says for constant epsilon and sufficiently small delta, one can achieve classification error $o(1)$, which is impossible for pure-DP algorithm. We will add this explanation in the revised version. Q3: The approach requires to solve SDP which is heavy for larger datasets. Q4: The experiment is not comprehensive and I find it not very convincing. A3, A4: When the datasets are large, repeatedly solving the SDP to obtain statistically significant findings does take a long time, which is also why we did not conduct experiments on larger datasets. Q5: The presentation is technically heavy. It would be helpful to talk about more intuitions and less calculations in the main text. A5: We will add more intuitive discussion on the formalization of SDP and some lemmas, and add intuitive comparison between the $(\epsilon,\delta)$-DP algorithm and the $(\epsilon,0)$-DP lower bound, etc. Q6: In Theorem 1, n and m are not quantified. Also, the quantification of $\sigma$ is not very clear — ''for every'' or ''exists''? A6: We will clearly state that Theorem 1 holds for "n-vertex and m-edge graph G" and explicitly point out that "there exists $\sigma$". Q7: In the experiments, it would be nice to define or at least explain what AMI and NMI are, and what do they indicate. I’m not even sure if larger value is better. A7: In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. AMI and NMI are two different forms of MI. Indeed, the larger the values are, the better the performances are. We will add this in the revised version. Q8: I found only arXiv version is cited for several papers — are they published in a conference? Please check and update. A8: Thanks for pointing this out. Indeed, some references have been published at conferences. For example, the cited Chen et al's work is published at NeurIPS 2023, and the cited Liu et al's work is published at COLT 2022. We will update these citations. Q9: You mentioned that your experiments are to somehow verify that ''when the noise added to the adjacency matrix by randomized response is balancing with its signal, the output of Algorithm 1 still has significant utility'', but I don’t see this clearly discussed. For instance, from what data did you see that the noise added by randomized response is balancing with its signal? And how exactly does your Algorithm 1 compare w.r.t. utility? A9: For $p$ between $0.2$ and $0.3$ and $q$ between $0.0$ and $0.1$, randomized response will, in expectation, blur the cluster and non-cluster edge densities. For example, for $p=0.2$ and $q=0$, the expected (empirical) $p'$ and $q'$ after randomized response (with $p_{RR}=0.27$) would be $0.36$ and $0.27$, so $|p'-q'|=0.09$. Considering $|p-q|$ as the strength of the clustering signal in the original graph, roughly half of it is shadowed by randomized response in the noisy graph. We agree that ''balancing'' for $|p-q|/2 = |p'-q'|$ is a sloppy term. We initially intended it as an exposition and motivation for the experiment, but we will add a more technical explanation. The utility is measured by AMI and NMI with respect to the ground truth clusters of the SBM. We will clarify this in the revised version as well. Q10: I may have missed something, but did you say the value of eps and delta that you use in the experiments? A10: Yes, please note that we mentioned it in ''Datasets and setup.'': $\epsilon = 1$ and $\delta = 1/n^2$.

We thank you for your reviews and address your questions as follows. Q1: I'm curious what's the relation of this well-clustered graph with stochastic block model? The SBM seems to attract much more research interests. Is the problem studied here a generalization of SBM, or a special case, or neither? A1: In general, SBM is a generative model, and well-clusterability is a structural property of graphs. In particular, edges in a well-clustered graph are not necessarily chosen independently with certain probabilities but can be added in an ''adversarial'' way. SBM can be parameterized so that it produces well-clustered graphs with high probability. On the other hand, there exist well-clusterable graphs that cannot be generated with high probability by any SBM parameterization (e.g., bipartite clusters, or clusterable graphs with constant average degree). In general, clustering on well-clustered graphs poses a more challenging problem. Q2: It would be very helpful if the authors can give some intuition & motivation of the SDP, in particular how the regularizer and the constraint (1) are designed. A2: The intuition of the SDP is the following. We would like to ensure a significant sum of vector distances for all pairs of points, and the objective is to minimize the vector distances between endpoints of all edges, thereby achieving a configuration where inter-class vector distances are large and intra-class vector distances are small. Considering a ground truth clustering $C_1, \cdots, C_k$ in a well-clusterable graph and a set of orthogonal bases $v_1, \cdots, v_k$. We can set the vectors associated with vertex $u$ to be $v_i$ if $u \in C_i$, then the objective can be upper bound by $2\phi_{out}m+\frac{8m}{\lambda}$, which reflects the number of edges crossing different clusters and the added regularizer part. The regularizer is added to ensure the strong convexity of the objective function, which in turn guarantees that the solution to the SDP is stable. We will add this discussion in the revised version. Q3: I'm curious why the DP noise is applied to the Gram matrix X rather than directly to vectors associated with each vertex? A3: The main reason is that we can only guarantee that the $\ell_2$-sensitivity of the matrix $X$ is small, or the dot products of vectors have small sensitivity. This is due to the fact that the objective function in SDP is strongly convex in $X$, which in turn guarantees that $X$ has small sensitivity by Lemma 3.1. On the other hand, we do not know how to bound the sensitivity of vectors. Q4: Proof of Lemma 4.4: The upper bound on $\sum_{i=1}^k|E(C_i,V-C_i)|$ is $\phi_\text{out}\cdot 2m$, not $\phi_\text{out}\cdot m/2$. A4: Thank you for pointing out this, we will fix this typo. Q5: Proof of Lemma 4.4: Could you give a detailed explanation on how the second smallest eigenvalue $\mu$ of $L_{G_{C_i}}$ can be obtained by minimizing the quotient given in the paper. A5: This is actually a known fact. That is, if $\mu$ is the second smallest eigenvector of the *normalized* Laplacian matrix, by its relation to the Rayleigh quotient, it can equivalently be written as the formula that we used in Lemma 4.4. This fact can be found in the book "Spectral Graph Theory" by Fan Chung (page 5, equation 1.5). We will add this reference in the revised version. (We will add the missing word *''normalized''* in front of ''Laplacian matrix''. ) Q6: In experiment the baseline is random response + SDP without regularizer. Why do you remove the regularizer? A6: The regularizer facilitates a trivial solution on the SBM to smooth and bound privacy. Since the input graph of the SDP is already DP after applying randomized response, the regularizer is not needed and would only worsen the quality of the result.

We thank you for your reviews and address your questions as follows. Q1: The condition "WELL-CLUSTERED GRAPHS" may reveal sensitive information in edge privacy. A1: The privacy guarantee in Theorem 1 holds for any graph i.e., also not well-clustered graphs. The reason is that the algorithmic framework we are using ensures that upon small changes of the input graph, the output of the algorithm does not change significantly, *regardless of the input's nature*. Therefore, the algorithm does not leak private information with respect to $(\epsilon,\delta)$-DP. Only the utility guarantee depends on the well-clusterable property. Q2: The authors claim that this submission is inspired by a recent work of Chen et al, so what is the main difference between this submission and Chen et al's paper in the technique aspect? A2: In the following, we abbreviate Chen et al.'s work as [CCDEIST]. Since [CCDEIST] focuses on SBM with $2$ clusters and we are focusing on well-clustered graphs with $k$ clusters, the SDPs in these two works are different. Furthermore, [CCDEIST] uses the signs of the first eigenvector of the noisy version of the SDP solution for the rounding and uses the probabilistic tools for the analysis, while our rounding is based on the spectral embedding and the k-means algorithm, and our proofs predominantly employ spectral graph theory. Q3: For two adjacent data sets (graph) D and D' differing in one edge, could it happen that D is well-clustered while D' is not? A3: Yes. Since for every well-clustered graph $G$ and not well-clustered graph $H$ (of the same size) there is a sequence of edge insertions and removals that transforms $G$ into $H$, there exist such two adjacent pairs $D, D'$ in the sequence. Indeed, it can happen that in a well-clustered graph, one cluster (expander) might contain a dangling edge, whose removal will cause the graph to be not well-clustered. However, note that the privacy guarantee in Theorem 1 holds for any graph, regardless if the input graph is well-clustered or not.