On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

Thank you for the helpful feedback! We address each concern here.

The authors require an upper bound on the maximum edge probability that is comparable to $p, q$ -- this type of assumption isn't necessary for other algorithms such as SDPs.

When the degrees are sufficiently high (i.e., $p, q$ are around $n^{-1/2}$), we do prove that even with arbitrary edge additions within clusters, unnormalized spectral clustering achieves perfect recovery (please see the DCM – Model 2, lines 202-211 on page 5 and the corresponding Theorem 2). This model actually allows more power than adding in-cluster edges to an SBM. Indeed, the adversary can be adaptive, meaning they can draw arbitrary internal edges after seeing the randomized crossing edges. As far as we are aware, such an adversary was not studied even for SDPs or other (more complex) polynomial time algorithms.

However, the stronger model above requires high degree (around $\sqrt{n}$) to guarantee recovery, and it is an open question if we can push this result to the case of $p, q \sim (\log n)/n$ (see the discussion in Appendix A). A promising general direction here is to develop a better understanding of entrywise eigenvector perturbations for high-rank signal matrices. To our knowledge, our analysis is the first to give such a guarantee, but it will be interesting to do this for larger perturbations.

They also don't achieve the sharp information-theoretic threshold of [ABH16] that other algorithms do.

Our bounds are within constants of the information-theoretic threshold, but yes, we do not know if it is possible to match it. Please refer to the response to reviewer e2Qn.

It is not clear that the nonhomogeneous SBM model proposed in the paper is a reasonable model for graphs that appear in practice because of this upper bound on the maximum edge probability and also the fact that no perturbations are allowed for the edges between different communities.

Note that even the "vanilla" SBM has been a useful model in practice, by way of developing algorithms, and our model is a strict generalization. Our results provide evidence that unnormalized spectral clustering is a useful algorithm even with a significant amount of perturbation (though our proofs come with the limitation of the upper bound on max edge probability or a high-degree requirement). At a high level, the reason to study semirandom models is to understand if a given algorithm has overfit to some statistical properties about its input that should be morally irrelevant; in this sense, we believe that even with the restrictions, our results show a good level of robustness for spectral clustering. (We also refer to the discussion in lines 65-72 of the introduction, and our response to reviewer e2Qn.)

Thank you for the helpful feedback! We address each concern here.

Adding the edge only inside the clusters or promoting the in-cluster edge probability will only increase the signal-noise ratio (SNR) for the SBM model(Abbe 2018).

This is typically the case for semi-random corruptions-- the SNR only improves compared to the uncorrupted (or purely stochastic) model. This means that the recovery problem is intuitively "easier", and it indeed is easier in an information theoretical sense. But as it turns out, algorithms for the stochastic case can fail. A classic example here is the semi-random planted clique problem, where a simple spectral algorithm can find cliques of size $\sim \sqrt{n}$ in the purely stochastic case, but it is known that the adjacency matrix-based spectral method fails under a monotone adversary and it is not known whether other spectral methods succeed to this threshold under the monotone adversary (see, e.g., pages 2-3 of https://timroughgarden.org/w17/l/l11.pdf).

Thus in our setting, it is not clear at all if the simple spectral algorithm (which has a reputation for being "brittle") should achieve perfect recovery when we add edges within clusters (in fact, by our Theorem 3, the normalized spectral clustering algorithm provably fails in such a model). So while it would be nicer to be able to show recovery under more general corruptions, even the simpler setting we considered requires several new ideas.

A comparison of the conditions of strong consistency for NSSBM with the existing model should help understand the paper better.

A comparison of these conditions can be found in lines 191-195 of the submission and in equations (14) and (15) in Appendix F (where we show additional empirical results): when $p,q = \Theta(\log n / n)$, the threshold we obtain is within a constant of that of the SSBM. We can emphasize this more in the final version.

Is it possible to extend the analysis to the model with variant choices of out-cluster probability for each pair of nodes such that $q_{v,w} \in [\overline{q},q]$? It seems trivial at least at the population level but I am not sure how the new change will affect the perturbation analysis.

This is a very interesting question, and it is posed as an open problem in Appendix A. In our current analysis, we crucially use the fact that the ideal second eigenvector can be easily characterized --- i.e., it is $u_2^{\star} = [-1_{n/2} \oplus 1_{n/2}]/\sqrt{n}$. Further, this means that the Laplacian corresponding the internal edge additions remains orthogonal to $u_2^{\star}$. But if we allow changing the out-cluster probabilities, then even at a population level, $u_2^{\star}$ need not have a simple structural form, which causes the current techniques to fail. We will add more of this discussion to the final version.

Thank you for the supportive review!

Could you please give an indication of which parts of your analysis could be tightened to yield sharp constants?

In the current analysis, the Lemmas B.5 and B.6 have constants that we have not optimized, for the sake of clarity in exposition. While it is possible to improve constants slightly by a more tedious analysis, it is an open problem whether they can be improved all the way to the information-theoretic threshold. This question is also conceptually interesting: for certain semirandom models and recovery regimes, the recovery threshold can shift [MPW16], whereas in other cases it does not. We will add this discussion to the final version of the paper.

Thank you for the helpful feedback and questions! We address each concern here.

One of the biggest problems with keeping the number of clusters constant and then providing results for "n" large is that in most practical situations, the number of clusters grows with n. In that sense of weak consistency, results that are available in the literature are much more appealing.

As you point out, this may constitute a gap between practical scenarios and the theoretical guarantees that are proven within the SBM community. To our knowledge, most of the literature that gives provable guarantees for this problem consists of results where $k$ is independent of $n$ [Abbe17, page 114].

This paper does not deal with weak consistency results. Can you just comment on performing this kind of analysis to the weak consistency case where one allows the number of clusters to grow.

As highlighted by the survey of [Abbe17], spectral methods actually do not succeed up to the KS threshold, and such thresholds in fact cannot be achieved under a monotone adversary [MPW16]. While there are spectral partitioning algorithms based on higher-order Cheeger inequalities (e.g. [LOT11]), these work with the normalized Laplacian and apply to a different generative model from the one we study. By virtue of our Theorem 3 (and our answer to your last question), these algorithms seem unlikely to be robust to the kinds of perturbations we study in this work. It would be interesting to see whether spectral methods can achieve the threshold obtained by [MPW16] under a monotone adversary.

One of the most important factors in studying spectral clustering under blockmodels models is sparsity. I could not find any comment about this in the paper.

The literature on block models often works in one of two regimes, the "sparse" regime where $p, q$ are $C/n$ for some constant $C$, and the "high degree" regime, where $p \gg (\log n)/n$. Our work falls into the latter setting, similar to many of the prior strong-consistency results.

Why is the bi-partitioning constraint? Is it because, when we consider top K eigenvectors, one needs to perform K-means which can introduce further problems?

Yes, if we consider more eigenvectors, simply considering the sign does not suffice for obtaining a partition. For example, the works on higher-order Cheeger inequalities need more careful partitioning algorithms to obtain guarantees [LOT11]. Also, to our knowledge, it is not known whether spectral methods achieve the information-theoretic bound for exact recovery in the case of $k > 2$, even for standard generalizations of the SBM to $k > 2$ communities.

Secondly, analyzing the k=2 setting is already quite non-trivial, e.g., proving that spectral algorithms achieve strong consistency for two communities was a longstanding open problem until relatively recently [AFWZ19]. While it is true that many papers in property-testing [CKKMP18] do consider the general setting of $k$, in the setting of SBMs, designing any algorithm for recovery for $k>2$ often requires much more sophisticated algorithmic machinery: like the recent result of [MRW24], STOC’24 (for general $k$), generalizing the result of [DDNS21], FOCS’21 (for $k = 2$) for the robust community recovery regime. Such results are less appealing in practice than those concerning spectral algorithms, which are commonly used.

The Cheeger's inequality based description of hard instances for the normalized case is nice but not difficult to perceive. Considering that we have higher-order cheeger inequalities, how do we extend this analysis to the multi-partition case? Just looking for a comment if authors happen to know about these results.

The Cheeger-based intuition of the hard instance for $k=2$ carries over to larger $k$: if the edges added by the adversary create a new, different, $k$-way sparsest cut, the embedding in the bottom $k$ eigenvectors of the normalized Laplacian should reflect (up to $poly(k)$ and square root losses) this new $k$-way sparsest cut as opposed to the planted one.

[LOT11] Multi-way spectral partitioning and higher-order Cheeger inequalities (https://arxiv.org/abs/1111.1055)

[MPW16] How Robust are Reconstruction Thresholds for Community Detection? (https://arxiv.org/abs/1511.01473)

[Abbe17] Community Detection and Stochastic Block Models (https://arxiv.org/abs/1703.10146)

[CKKMP18] Testing Graph Clusterability: Algorithms and Lower Bounds (https://arxiv.org/abs/1808.04807)

[AFWZ19] Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank (https://arxiv.org/abs/1709.09565)

[DDNS21] Robust recovery for stochastic block models (https://arxiv.org/abs/2111.08568)

[MRW24] Robust recovery for stochastic block models, simplified and generalized (https://arxiv.org/abs/2402.13921)