Exact Community Recovery under Side Information: Optimality of Spectral Algorithms

We thank the reviewer for a thoughtful review and their constructive feedback on the work! Below we address the weaknesses pointed out in order.

1. Indeed, the reference of [Abbe, Fan, Wang 2022] is an important one, which we missed. We will include it and compare our work. As mentioned in the common response, we will include the simplified expressions of $I^*$ whenever possible to enhance interpretability.
2. Please see the common response where we elaborate how the distribution parameters can be estimated from $A$ and $y$. It is not clear how to estimate $\alpha$ in the BSC channel if it is not already given.
3. Please see the common response for details on the multi-community extension.
4. Yes, as mentioned in the common response, we will include numerical simulations verifying the optimality of spectral algorithms.

Thank you for catching some typos! We will fix all of them and carefully proof-read the final version

• Regarding ''unification'' and generality of the results:

As for the “unified proof framework” language choice: we mean the entire framework of genie-aided estimation (done generally) and its connection with the spectral algorithm (done for SBM and ROS, and general side information). See Figure 2 for a summary. We believe this is still very general compared to the prior works with algorithmic results. We further expand on the analysis of spectral algorithms to elaborate on the difficulty involved in further generalizing. The analysis has the following crucial steps.

1. Genie scores and its success with margin: We define the notion of genie scores (Section 4) and show that they have the correct sign with sufficient ``margin” above the IT threshold (Appendix D, D.1). This step has nothing to do with the spectral algorithm and hence derived more generally for any block model GBM (Definition 2.1), i.e. in terms of the definitions of the laws $P_{+}, P_{-}, Q$.

2. Design of spectral algorithm and genie-spectral score approximation: This is the step where we specialize in the SBM and ROS. In order to handle other models, we discuss a roadmap in Appendix A.1 (future extensions). There should be a possibility of handling more general distributions from the exponential families, where the log-likelihood is linear. (Note that even the algorithm of Dreveton et al. without any provable guarantees is also only for exponential families). However, the main bottleneck is the entrywise behavior of eigenvectors [Abbe et al. 20], which is crucial for the spectral algorithm and holds under some set of abstract assumptions A1-A4 (lines 1242-1252) in Appendix E. We verify these assumptions in Appendix E for ROS and SBM. As these assumptions are not simple and intuitive, we decide to just focus on ROS and SBM because (i) it already brings across the key idea behind the genie-spectral connection (ii) these already include important cases that have received their own special treatment in the literature: general two community SBM, $\mathbb{Z}_2$-synchronization, Submatrix Localization. The interesting thing is that we can handle general side information channels.

• Section 3.1: That’s a good suggestion. The information-theoretic limit in Section 3.1 is stated in a slightly different way than from Dreveton et al., having made some simple observations. We do not consider them as the main results and will exclude them from Section 3.

• IT threshold expressions: The expressions for $I^*$ when simplified, have simpler intuitions of SNR. Under no side information, according to the parameterization in Def 2.3, it is well-known that for SBM(½,$a,a,b)$, the threshold $I^*=(\sqrt{a}-\sqrt{b})^2 /2$. For ROS($\rho, a, b$), the threshold is given by $I^*=(a-b)^2 (\rho a^2+(1-\rho)b^2)/8$ and also can be seen as SNR. Under side information channels, the additional term introduced $D_t (S_{+} \Vert S_{-})$ has an intuitive formula for GF, BEC, and BSC (derived in Appendix C). As alluded to before in the common response, we will include simplified expressions whenever possible to enhance the interpretability of the results. The algorithm is not generally concerned with calculating $I^*$. For the specific cases of models and side information considered, the formula of $I^*$ has closed-form expressions and hence can be computed. The algorithm is agnostic to the threshold and operates on the input $(A,y,$ model-parameters$)$; only whether the algorithm succeeds or not is characterized by the recovery threshold.

• Proof technique: The main novelty in the proof technique is in the genie-spectral connection. Overall, we believe this insight should help us in the design and analysis of spectral algorithms going forward. See future extensions in Appendix A.1 and the discussion in Section 6.

Questions: Below we answer the questions in order.

1. Please see the common response---we will include numerical simulations for SBM and ROS, with three side information channels. We have not performed experiments on real-world datasets. As the real-world networks may not really be satisfying the modeling assumptions of SBM, this may require delving into the robustness of the algorithm to the modeling assumptions, which is beyond the scope of this work. For synthetic networks that are really sampled according to our models, the algorithm should indeed succeed up to the sharp recovery threshold as we have theoretical guarantees.
2. Runtime: Please see the common response. Our algorithm has a ``nearly linear” runtime.
3. Multi-community extension: We refer to the common response for the detailed answer on this.

We thank the reviewer for their time in reviewing our submission and are happy to address their concerns!

Summary and Contributions

New Results: The main results of this work is to provide optimal spectral algorithms for the exact recovery problem under node-attributed side information in the two community block models with Bernoulli and Gaussian edge observations (lines 17-19, 84-89). The work of Dreveton et al. has characterized the IT limits and their proposed algorithm (requires edge observations are from exponential families) has no theoretical guarantees.

Algorithm: The main challenge here is that there could be many ways to use side information, and we are interested in the one that optimally combines the signal from $A$ and the side information $y$, to achieve the new IT threshold. Our focus here is to design a spectral algorithm in particular. See lines 90-122 as to how different setting-specific choices have been adopted in designing spectral algorithms to achieve optimality e.g. (a) just sign thresholding 2nd eigenvectors for symmetric SBM [Abbe et al. 2020] (with adjacency matrix) and [Deng et al. 2021] (with laplacian) Vs carefully designing linear combinations of eigenvectors for PDS [Dhara et al. 2022b] (b) the special choice of encoding in the censored variant of the problem [Dhara el al. 2022a] and (c) combining eigenvectors of the two matrix representations of the same network to handle general censored SBM [Dhara et al. 2023]. Notably for the uncensored variant as we study here, even under no side information, the optimal spectral strategy was not clear; in particular it was not apparent whether one matrix representation suffices or whether we need two as in the censored counterpart [Dhara et al. 2023]?

Designing optimal spectral algorithms is a delicate issue and the availability of side information makes it an interesting problem as to what is the optimal strategy to use it. See lines 116-122 for the auxiliary goal of this work. That brings us to our main technical novelty of the work.

The genie - spectral connections and proof technique: The main novelty of the work is in rigorously establishing the connection between the spectral estimators and the genie aided estimators (the entire Sections 4 & 5). Note that these genie-aided estimators in Eq 6 are very powerful due to the availability of a genie that reveals all but the label that we are trying to estimate. We are able to design spectral strategies that can mimic the genie by approximating the genie scores in Eq (7), which in words is the log likelihood ratio of the $i^\mathrm{th}$ label being +1 and -1 given the edge and node information, and also the remaining labels (due to the genie). The spectral algorithm sketched in Algorithm 1 computes the statistics $z_{\textnormal{spec}}$ that approximates $z^*$ in $\ell_\infty$ norm (without the access of the genie) directly from the eigenvectors of $A$.

As a consequence of this connection, we immediately have an optimal strategy to incorporate side information, mentioned in Eq (1). See also Lemma 4.2 and lines 368-377.

We continue the response as a new comment below. We address the specific points raised by the reviewer in order.

We thank the reviewer for their quality feedback and acknowledging the key contributions of our work! We indeed faced some difficult choices due to the page limit and had to delegate some important points on the design of spectral algorithms to the appendix. As mentioned in the common response, we will adjust the presentation such that the key ideas involved in designing the spectral algorithms therein are well-highlighted in the main text. We also appreciate the feedback on the spelling errors, and will make sure to resolve them in the final version.

We thank the reviewer for their time and the thorough review of the submission! Below we provide some clarifications on the weaknesses.

• Derivation of the genie score: As we mentioned in the common response, we will include important details in the main text, in particular the derivation of $z^* \approx Aw+ \gamma \mathbf{1}$. The expressions of genie scores will take this form for the distributions from the exponential families more generally. Roughly speaking, (i) $A$ corresponds to the sufficient statistic, (ii) the vector $w$ is a vector with block structure whose entries are the ratio of canonical parameters for $(P_+, Q)$ and $(Q, P_-)$ respectively (iii) the scalar $\gamma$ is some weighted combination (depends on $\rho$) of log-ratio of normalizing constants of $(P+,Q)$ and $(Q,P_{-})$. Therefore, the vector $w$ and $\gamma$ can be explicitly computed from the model parameters. We will include this discussion in the final version.

• Estimating model parameters: See the common response where we describe a method to estimate the parameters when they are unknown. Specifically, for SBM and ROS, the estimated model parameters (calculated in this way from $A$) will be close to the true value with an additive error of $o(1)$ with high probability. This suffices for the spectral algorithm to still continue to succeed when we use the plugins.

• Numerical Study: Please see the common response. We will include a simulation verifying that the spectral algorithm achieves the IT threshold. The comparison with two-stage approaches is beyond the scope of this work because: (i) Even the two-stage algorithm has nearly linear runtime and is a good algorithm. Our work does not aim to establish a practical advantage of the spectral algorithm over it (ii) Even if there is an advantage, the two-stage algorithm so far has been only presented for SBM and PDS with BEC and BSC channels [by Saad and Nosratinia 2018,20]. It is not too difficult to design the algorithm more generally given our framework. However, we strongly feel this should be done with more careful attention to the details along with theoretical analysis of its optimality, which is beyond the scope.

Questions

1. Well-defined L(t): Note that the way we define $P_+, P_-, Q$ are the sequences of distributions that vary with $n$, e.g. this is the case in both SBM and ROS. We explicitly mention $L(t)$ is well-defined for rigor, to avoid having "weird" pathological sequences of distributions i.e. different distributions for odd and even $n$ s, etc; otherwise, we expect it to hold more generally, whenever the $P_+, P_-,Q$ converges in distribution as $n \to \infty$.
2. The degree-profiling algorithm: this algorithm is just using the side information $y$ as proxy for the genie given labels $\sigma_{-i}^*$. This is briefly described in lines 413-417. The caveat in Remark 5.1 essentially says that this strategy is not going to succeed in recovering labels, if side information is absent or "weak" even though the recovery is possible just from $A$, because it just relies on the signal from $y$ to attain the first preliminary labeling.
3. w in the span of eigenvectors: This is a good question and the answer is subtle. When the rank of $A^*$ is the same as the number of communities, it is always possible to express $w \approx c_i u_i^*/\lambda_i^*$. This is because $w$ is a block vector with $K$ blocks and so are $u_i^*$ s. And due to the linear independence of $u_i^*$ s, all $K$-block vectors are in the span, including $w$. However, when rank$(A^*)<($# communities$)$, there is no such guarantee. In our cases, we were still able to achieve this though.

(a) ROS: This is a rank-1 model. However, the genie linear combination vector $w$ is along the direction of $u_1^*$, and thus we are able to emulate the genie.

(b) SBM rank-1: The case when $a_1a_2=b^2$. In this case, the genie vector $w$ is not along the direction of $u_1^*$ (contrary to ROS) but it turns out that $w$ is a deterministic vector that does not depend on the locations of $\sigma^*$. This allows us to still approximate the genie scores, though without a "spectral approach" strictly speaking i.e. without using the eigenvectors. See Algorithm 6 and lines 2077-2080, where we handle the rank-1 case separately.

When rank$(A^*)<($# communities$)$, we are not sure if there is any general condition that ensures this happens. Thus, we critically put this in Requirement 2 in line 775-776 in future extensions in Appendix A.1.

4. Yes, as specified before, the parameters $\gamma, a_1, a_2, b$ can be estimated from the adjacency matrix with an additive error of $o(1)$, which suffices for the spectral algorithm to continue to succeed when used as a proxy.

5. The region of $I^*<1$ corresponds to the impossibility region. Did you mean whether we can split the region $I^*>1$? Yes, we can let $I_0^*$ as the expression of IT threshold under no side information, and divide $I^*>1$ into two subregions $I^*_{0}>1$ and $\lim_{n \to \infty} \left( D_t(S_+ \Vert S_-)/\log n \right) > 1-I_0^*$. More specifically, for ROS with BEC and BSC channels, there is a nice phase diagram which we will include in the updated version.