Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
Authors: Julia Gaudio
Nirmit Joshi
Venue: ICLR 2025 Poster (2025)
Keywords: Community Detection
Spectral Algorithms
Side Information
Primary area: learning theory
TL;DR: We present optimal spectral algorithms for exact recovery problems that can incorporate node-attributed side information, for popular Gaussian and Bernoulli matrix models including SBM, submatrix localization, and Z_2 synchronization.

Abstract: We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed *side information*. We allow for a very general side information channel for node attributes, and for pairwise (edge) observations, consider both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, Submatrix Localization, and $\mathbb{Z}_2$-Synchronization as special cases. A recent work of Dreveton et al. 2024 characterized the information-theoretic limit of a very general exact recovery problem with side information. In this paper, we show algorithmic achievability in the above important cases by designing a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the pairwise observation matrix. Using the powerful tool of entrywise eigenvector analysis [Abbe et al. 2020], we show that our spectral algorithm can mimic the so called *genie-aided estimators*, where the $i^{\mathrm{th}}$ genie-aided estimator optimally computes the estimate of the $i^{\mathrm{th}}$ label, when all remaining labels are revealed by a genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in a recent line of work.

Published as a conference paper at ICLR 2025
EXACT COMMUNITY RECOVERY UNDER SIDE INFOR- MATION: OPTIMALITY OF SPECTRAL ALGORITTMM
Julia Gaudio
Nirmit Joshi
Northwestern University
Toyota Technological Institute at Chicago ni smit@ttic.edu
julia, wwwudio@oortwwweeee.e.eeooeoeooe edu
ABSTRACT
We study the problem of exact community recovery in general, two-community block models, in the presence of ante-batributed side information. We allow for a very general side information channel for node attributes, and for pairwise (edge) observations, consider both Bernuuli and Gaussian matrix models, capturing the Stochastic Block Model, Submatrix Localization, and Ez-Synchronization spe- cial cases. A recent work of Dreveton et al. (2024) characterized the information- theoretic limit of very general exact recovery problem with side information. In this paper, we show algorithmic achievability in the above important cases by de- signing a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the pairwise observation matrix. Using the powerful tool of entrywise eigenvector analysis (Abbe et al., 2020j, we show that our spectral algorithm can mimic the so called genie-aided estimators, where the tt genic-aide estimator optimally computes the estimate of the 7th la- bel, when all remaining labels are revealed by genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in recent line of work.
INTRODUCTION
In this paper, we consider inference problems of the following form: there is an unknown partition
of the set [n] == 21,2,.... ... n into two communities, denoted (C+,C_) with (p, - p) fraction of vertices respectively for p E (0, The community assignments are encoded by a vector o" e [=1]". We observe symmetric matrix A E _ax=, which is specified by three distributions: P+, P_, and Q The entries of A are independent (up to symmetry), such that Aij ~ P+ i,j Ay ~ P if i E C_, and Ai Q otherwise. One famous example is the Stochastic Block Model (SBM), where P+ = Bern(p1), P_ = Bern(p2), and Q = Bern Other prominent examples include Zg synchronizaaiinnn and submatrix localization, in which P,. P_, Q are Gaussian distributions. Given the observation A, the goal is to exactly recover the unknown a*.
j E C+.
2015 Abbe al. [0016 Hajek al., 2016 Abbe 2017: Bandeira et al. 2017]] Javanmard et al. 2016 Cai et al. 2017), a fairly complete picture of the fundamental limits exact recovery and algorithmic achievability is known. In recent years, with practical considerations, exact recovery has also been studied in different variants such as node-attributed side information (Saad & Nosratinial 2018 2020 Deshpande et al. 2018 Abbe et al. [2022] Dreveton et al. (2024), partially censored edges (Abbe et al. 2014 Hajek et al. 2015
After long line of research (Decelle al. 2011 Mossel
Moghaddam et al. 2022 Dhara et al. [022a]] (023), multiple correlated networks (Racz & Sridhar
2021 Gaudio et al. (022), spatially embedded networks (Abbe al.) [021] Gaudio al. 2024bb
etc. See Appendix A.3 for different variants considered more broadly in community detection liter-
ature beyond exact recovery.
In this paper, similar to Dreveton et al. (2024), we consider the setting of node-attributed side infor- mation, where we given a side information vector y y" in addition the pairwise observa- tion matrix E Raxn The side information is drawn according to a pair of distributions (S+, S_), where for each i [ni]. obtain
y/1 S+ i C+, or S i E C.,
where the observations are independent, conditioned on the communities. The setup captures several interesting special cases:

---

Published as a conference paper at ICLR 2025
1. Gaussian Features (GF): For each node, we have vector of d real-valueds attributes. This is modeled as J = IR and both S+ and S_ are parameterized multivariate Gaussians in dimensions.
2. Binary Erasure Channel (BEC): The true community assignment of some subset of ver- tices are known (partially observed labels), modeled as y = {-1,0, +1} and y is formed by passing o* through binary erasure channel.
3. Binary Symmetric Channel (BSC): We have "guess" on community assignment of each vertex (partially correct labels) and interested in recovering the true assignment. This is modeled as passing o* through binary symmetric channel with } E {-1,+1}.
Exact recovery under BEC and BSC side information channels was first studied by Saad & Nos- ratinia 2018 2020) for two special cases of Berouuli pairwise observations; symmetric SBM (P. P_ 172) and Planted Dense Subgraph (PDS) (P_ = Q). The work of Dreveeon et al. 2024 recently studied very general recovery problem, allowing generic distributions (P+,P-,4
and side information laws S-). satisfying certain technical assumptions. They derived sharp information theoretic thresholds for exact recovery under side information in a unified way, and showed that the optimal Maximum A Posterior (MAP) estimator succeeds down to this threshold. However, naive MAP estimation requires a brute-force computation, and thus it is not efficiently (poly-time) computable in the worst case. Therefore, it remains important to design efficient algo- rithms. We note that Dreveton et al.] also proposed an efficient, iterative likelihood maximization algorithm when node and edge observations are from an exponential family of distributions, though without theoretical guarantees on the performance. In this work, our primary goal is:
Objective 1: To design efficient algorithms that are provably optimal i.e. succeed down to the information theoretic threshold.
We note that the work of Saad & Nosratinia 2018 2020) designed provably optimal algorithms only for the two special cases they studied (symmetric SBM and PDS), and only under BEC and BSC channels. They use two-stage strategy that first determines almost exactly correct labels, followed by a refinement step achieving exact recovery (see Appendix (appendixAA.3...... this work, our focus will be on designing single-stage spectral algorithm without any refinement step that directly achieves exact recovery and in much greater generality. In particular, we consider any side information channel with distributions SL) but restrict to the following pairwise distribution laws
1. Rank One Spike (ROS): The distributions Pt. P__, and Q are Gaussian distributions, capturing Zg-synchronization and submatrix localization as special cases.
P_, 2. SBM: The general two community stochastic block model where P-, and Q are any Bernoulli distributions.
Background on spectral algorithms for exact recovery. Spectral algorithms were popularized by classical works such as McShemy's algorithm for community detection (MeSherry 2001) and the planted clique recovery algorithm of Alon, Krivilevich, and Sudakov (Alon et al. 1998). In
recent years, attention has shifted to spectral algorithms without the need of combinatorial cleanup phase. This line of work was initiated by the influential work of Abbe, Fan, Wang, and Zhong (Abbel 2020), who showed that in the symmetric, balanced SBM, simply thresholding the second leading cigenvector U2 of the adjacency matrix at 0 gives the correct community partition with high probability. In order to analyze the vector u2. Abbe et al.] developed the technique of entrywise eigenvector analysis, which characterizes the entrywise behavior of eigenvectors of matrices whose expectations are low-rank.
Following Abbe et al. (2020), series of papers used the entrywise eigenvector technique to give strong guarantees for spectral algorithms. For example, Deng et al. (202I) showed that, in the symmetric SBM, using the Laplacian instead of the adjacency matrix also yields an optimal al- gorithm. Another line of work Dhara et al.] (2022a] 2023) considered the censored variant of the problem, where the status of some edges is unknown. Even for the censored variant, they show that
While our side information channel laws are general, we note that the information theoretic limits of Dreveton et al. (2024) are in even more generality. Namely, they consider (i) more general distribution families (P+.P_, ②) and (ii) the case of more than two communities. In Appendix A.2, we shall describe how our spectral algorithms can be further generalized to (i) any (P+, P-, Q) coming from exponential families (with additional requirements), and (ii) more than two communities.
2

---

Published as a conference paper at ICLR 2025
spectral algorithms optimal, where the encoding of the unknown edges is chosen carefully to achieve optimaliy. Perhaps surprisingly, [hara et al. (2023) showed that for this censored variant of the problem, to handle cases beyond the symmetric SBM (P+ P-. = 1/2) and the PDS (P- = 2), any clustering algorithm based on a single adjacency matrix does not succeed down to the infornation-theoreiic threshold. Instead, the authors devised a spectral algorithm which forms two matrix representations of the same network and takes a carefully chosen linear combination of their cigenvectors to achieve optimaliy, All these results their core rely on the entrywise behavior of eigenvectors (Abbe et al. (020).
This raises several closely related questions: what governs the optimality of these seemingly differ- ent problem specific choices? Is there some principle behind designing new algorithms in related settings? For example, for the standard uncensored variant as we study here, the spectral algorithm for general two community SBM is unknown even when there is no side information. Do need two matrices like its censored counterpart (Dhara et al. 2023 To answer these questions, another auxiliary goal of this work:
Objective 2: To develop a unified perspective on the optimality of these spectral algorithms.
1.1 OUR CONTRIBUTION
Spectral Algorithms. We propose simple spectral strategy of computing the top eigenvectors (top one for ROS and top two for SBM) of the observation matrix A and take an appropriate linear combination. When side information y is also available, we incorporate it by shifting the eigenvector combination by the log-likelihood ratio vector of side information:
S+ log
S+ S__
(1))
(
SS (++(
(v) S
E (TR U (#) such that log
= loog
(1)
S__ (v:)
followed by prescribed thresholding.
The main technical novelty lies in establishing a rigorous connection between the spectral estimator and the so-called genie-aided estimators, where T genie-aided estimator optimally computes the 7th label, where the rest of them, denoted by o",, are revealed by a genie. Using the entrywise eigenvector technique (Abbe et al.] 2020), the leading eigenvectors of A (along with side information use prescribed above when they are available) produces vector whose T entry is well-approximated by the statistic computed by these genie-aided estimators in each of the settings. Thus, the spectral algorithm without any clean-up step is able to mimic the genie, and therefore achieves exact recovery down to the information -teeoatiionthhoortiic limits. Moreover, our algorithm is highly efficient with nearly linear runtime for the respective setting (see Remark (.3).
show that taking an appropriately weighted sum of
Models without Side Information. We note that even in the case of no side information, deter- mining when a single stage spectral algorithm without any clean up stage can succeed is of interest to the learning theory community. Our results fill the complete picture in important remaining cases such as the general SBM (beyond the symmetric case with P = P_ P = 1/2 Abbe et al. 2020 and the Planted Dense Subgraph (PDS) with P_ Q (Dhara et al. 2022a ). Most notably, un- like its censored counterpart (Dhara et al. 2023), one does not need two matrix representations to achieve optimality. In fact, the strategies of Abbe et al.] (2020); Deng al. (202T): Dhara et al.
(202a b) 2023) are essentially mimicking the genie in their respective settings. See the discussion Appendix A.2 for more details.
Unsupervised vs Semi-supervised Learning. The presence of side information turns commu- nity recovery from an unsupervised learning problem into semi-supervised learning problem. Therefore, another related perspective is to investigate the effectiveness cup-suuper learning approaches over unsupervised ones e.g. (Jiang & Ke/ [003)] Wu al.] [022] Ni et al.) 2024). We note that, from this perspective, investigating other relaxed goals such as weak or almost exact recov- ery could provide more satisfying picture, as the exact recovery is a very demanding criterion. The primary message of our work is that, for the exact recovery goal, there are simple extensions of the spectral algorithm that optimally combine the signal from A and the side information y. achieving the new sharp -nforrition-theorrtii limit provably using efficient algorithm.
Organization. Section 2 contains our models and other preliminary setup. Our main results are stated in Section 3 The genie-aided estimators are introduced in Section 4 which show how to
3

---

Published as a conference paper at ICLR 2025
mimic using spectral strategy in Section Future directions proposed in Section 6 The proofs are postponed to the appendices.
PRELIMINARIES
2.1 MODELS
We first introduce the General Two Community Block Model (GBM), which captures the special cases that we consider.
Definition 2.1 (General Two Community Block Model (GBM)), For any p E (0, 1) and distribu-
tions P+, P-, and Q, we say that (A,a*) ~ GBM, (p, P+, P_, 2). where A E RRuxn and o² E { td are sampled as follows. Each coordinate of a² is sampled i.i.d. such that Po(; = +1) [+11==p will
and PP(o;
the notation C+ := ii of +1} and C_ C_: = (i o +1}. Conditioned on o², we sample A, a zero diagonal symmetric matrix with n, we have
1)
Moreover,
independent entries, such that for 1 S
As P+, if 4.jECH Au ~ P-, if i.jeC Aig ~g 2, otherwise.
In the above definition, restrict to distributions which are either (i) continuous distribution or (ii) a finite, discrete distribution. Thus, P+(,), P.)... 2(.) also denote the corresponding probability density function or probability mass function, respectively. We will consider special cases where the distributions P_. 2) are either all Gaussian or Bernoulli distributions. The specialized definitions given below.
Definition 2.2 (Rank One Spike (ROS)). Fix any E (0,1) and a, b E R such that max [a), [6]] > We say that o*) ) (ÓS a. b) if they are sampled as follows. First sample o* as mentioned for GBM. Conditioned on a" consider the vector v" E {{a, 6)"h such that for E [n]
t = 1l0 = + 10; =-1..
Finally, conditioned on o², we gel independent noisy measurements for every i < j of the following form.
logn Au 17 v
+ Waj. where Wi i.d. 1).
n
Note that the model ROS, (p, b) is special case of GBM, (p. (p.P., P-,P_, by taking
a² log 1 P_ =N P-=N(11 logn n ) and Q W ab
log n
P4 = N
Taking b = O yields version of the Gaussian submatrix localization problem Hajek et al. (2018). for which the goal is to recover a submatrix of elevated mean (corresponding to the entries in C.). Taking -b yields the Zz-synchronization problem Bandeira et al. (2017) after rescaling; see
Remark A.2 Our scaling choice allows both submatrix localization and Fe-synchrronzzttion to be handled under unified model. We also consider the Stochastic Block Model (SBM) in the logarithmic-degree regime, which is the relevant regime for exact recovery.
Definition 2.3 (Stochastic Block Model (SBM)). Fix any p E 10.1) and 01, a2, b 0. Then the model SBM,, (p, a1, 022 b) is special case of GBM,, P-, Q) with
P+ Bern (1 log n
and Q = Bern bblog 02 log
P_
Bern
n
n
Finally, we consider a generic side information channel.
Definition 2.4 (Side Information (SI)). For any domain y, distributions (S+, S_) supported on Y, and a² {+1)", we say that y SI(o" S_), where y E ) such that for any i E [n))
yi ~ S., if = +1 and ~ S_ S_iff - --1
The entries (us)ie(m) are independent conditional o*. We assume that the likelihoods (y:) and S_ (y() are computable in O(1) time.
Definition 2.5 (Gaussian Features (GF)), The model y ~ GF,a".U,, U_ _0) for U+. U_ E Rd and o2 T²Ta) and S_ o(v_,02Ta)
d² > 0 is special case of SI with y Rdd and S+ NN
4

---

Published as a conference paper at ICLR 2025
Definition 2.6 (Binary Erasure Channel (BEC)). For any o' {=1}" and (0, 11, we say y ~ BEC c) where each entry of a² is erased to 0, independently with probability e, to form y E (-1,0, +1}".
Definition 2.7 (Binary Symmetric Channel (BSC)). For any o* E {+1}" and a E (0, 1/2), we say y BSC(a", a) where each entry of o* is flipped independently with probability a, to form E (+1}".
(a) BEC side information
(b) BSC side information
Figure 1:
Visualization of BSC and BEC side information. The red-colored, blue-colored, and uncolored vertices have side information labels of +1, 1, and 0 respectively.
2.2 EXACT RECOVERY.
Our goal is to exactly recover the community labels o" given the observation matrix A and the side information y when available, as formalized below.
Definition 2.8 (Exact Recovery). We say that an estimator â succeeds if
(i) ā {+o"} when P+ = P_ = 1/2 and there is no side information (the symmetric case);
(ii) â = o", when P- # P- or + 1/2 or side information is present (non-symmetric case).
Otherwise, we say fails. We say that â achieves exact recovery lim PP succeeds) 1.
Note that in the symmetric setting described in Definition 2.8 it is not possible to recover o* with high probability, and we can only hope to recover the partition. In all other cases, we wish to recover the labels and not just the partition. All our positive results will demonstrate recovery in this strong sense. The optimal predictor for any model and side information is the one which has maximum posterior probability given the observation matrix A and the side information y. when is present.
Definition 2.9 (MAP Estimator). Consider the observation matrix A and the side information from some side information channel. We define the Maximum A Posteriori (MAP) estimator as
ŌaP arg max "' A)
oE(L13"
When no side information is present, define ŌMAP arg max Pooo' AA)
2.3
INFORMATION THEORETIC THRESHOLD FROM DREVETON AL. 2024)
We now discuss the inoommation-thoorttii limits of exact recovery derived in Dreveton et al. (2024)
our notation. Deñne the Chernoff coefficient across the pair of communities as
(1- CH, cH((+.-)= [100=10000001110--+++ - -10000000000010000-000000-1
... (
Here (A) is the Rényi divergence order t between any two laws (A, B), such that they are either both continuous discrete, is given by
A(x))
(x((I))) = (1 11-1)
log E
(4)
208
B(x)
Define the limit L 1) + Rxo U {+00} by
I(t)
lim
n
CH,(+,-)
(5)
log
5

---

Published as a conference paper at ICLR 2025
We restrict ourselves to the laws such that L(t) is well defined characterized by
Then the information theoretic limit
I sup L(t),
(6)
rE(0.1)
where by convention, we consider the supremum to be +00 if L(t) is unbounded in t E (0, 1) or
there exists (0, 1) such that L(t) +00. Then the following proposition is minor variant of the two community case of (Dreveton et al. 2024, Theorem 1), characterizing the fundamental limit for exact recovery for the GBM.
Proposition 2.10 Drevetoo al. (024)). Lei p (0,1) and (P+,P_, be probability laws.
Let (A, (pM P+. P..P.... 2) and we observe A. Optionally, for side information laws
(-+, we observe y SI(o" S-. We assume the laws are such that I" (6) is well- defined. Then
1. If then the Maximum A Posteriori estimator oww achieves exact recovery.
2. Additionally, if Ia < 1 and the function L(t) is strictly concave then no estimator 5 achieves exact recovery.
This variant follows from (Dreveton et al. 2024 Theorem by observing that the success of MAP proof does not rely on the strict concavity of (t) and the proof goes through even if 1" too.
The impossibility result is completely equivalent theirs. We discuss the necessary proof changes in Appendix A.4 We note that the case of no side information can be realized by considering side information laws S-) that always deterministically output O; in this case D.(S+ ||S_) 0.
Finally, this information theoretic limit in (6) can also be interpreted as a signal-to-noise ratio; we discuss this interpretation in Appendix A. for the resulting expressions both ROS and SBM, and for each side information channel BEC, BSC, and GF.
3 MAIN RESULTS: ALGORITHMIC ACHIEVABILITY FOR ROS AND SBM
The main results of the paper are to design an optimal spectral algorithm for ROS and SBM.
Theorem (Optimality for ROS). Fix p E (0, 1) and a, R such that max aa. |b} > 0. Ler (A,a*) (O, a. b). Optionally, consider side information channel y SI(o" S S_) such that T" in (6) is well-defned. Then there is a spectral algorithm (Algorithm that returns the estimator Spec which achieves exact recovery whenever 1
2. Smmttmiiratun with GF Chaand
Syndimicalitn with BBC Channe
2. Syncheetization with BSC Channel
NNo de Informatoo GF Channel
Informaion SEC Channel
Information BSC Chantel
Figure We consider the F2-Synchronizattin model which is ROS., (1/2,a, aa). With n 300, each type of side information channel of "strength" (see Appendix [A we validate the performance of the spectral algorithm over N = 50 trails over grid of values for (8, a). Lighter pixels correspond to higher rate of success. The blue and red curves are theoretical thresholds with and without side information respectively.
Theorem (Optimality for SBM). Let E (0,1) and a1, 01,02, > O. Let (A,o") SBM, (p. 01 022 b). Optionally, consider a side information channel y ~ Sl(aa S4.S-) such that I" in (6) is well-defined. Then there is a spectral algorithm (Algorithms' 5 and 6 that returns the estimator âsee which achieves exact recovery, whenever I* 1.
In Appendix C. we will verify that for both SBM and ROS, the function L(t) (and thus also I*) is well-defined and L(t) is strictly concave for each (i) no side information (ii) GF, BEC, and BSC
We expect Itt) be well-defined for most sequences of laws, e.g. ROS,, SBM, We mention this explicitly just for the formalism, and to rule out pathological sequences of laws that do not converge co.

---

Published as a conference paper at ICLR 2025
channels. This along with Theorems 12 and Proposition 2.10 establissss that the spectral algorithm succeeds up to the theoretical results (see Figure and Appendix/A.I).. The main novelty of our analysis is to establish the rigorous connection between the spectral estimator and the so-called genie-aided estimators, which we now discuss.
limit these settings. We also rum simulations to verify our
GENIE-AIDEE ESTIMATORS
In the genie-aides aide setting (see e.g., Abbe 2017 ), we suppose that all labels but the 2th are known, and the goal is determine the jth label. More formally, let o=, denote the true labels, apart from o. The optimal estimator for the 7th label is given by
[1, if P(a = +1 +1 A,,, 2 F(o = = A,y,
Gen.
11, otherwise.
(where the conditioning on is omitted when there is no side information present). Moreover, we say that am., fails on an instance the posterior probability of the incorrect label is strictly greater than the posterior probability of the correct label. The following lemma rigorously establishes the intuitive claim that the failure of some genie-aided estimator implies the global MAP also fails.
Lemma 4.1. Let P GBM, (p. P+,P- Q) Optionally, let y formation for any laws S-),S_) over Y. Define the genie-aided estimators {ōamn i E [n]] and MMAP the respective model. Then
(0,1) and P+. P+.P-,9 be any distributions.
Let (A,a") ~
(S.SS) in y where y E 3" is the side
P( E [nx] Ocen, fails) S Po( fails).
Genie scores. We form vector z" E (IR U (=x)))" called the genie score vector, where x records the log of the ratio of posterior probabilities of the label of given o², by a genie, That is,
P(ao +11 A, A, = log P(o = -1 A,
P(a ++1 | A,
or 2 =logg P(o7 = = -
(8)
in the cases of side information and no side information respectively. Then the optimal genie- based estimator corresponds to d sgn(2;). Throughout the paper, we treat log as function from [0, oo] to the extended real line and implicitly use standard conventions of extended real line algebra. See Appendix B.I The following lemma gives the form of the genie scores without with node-attributed side information. Here we define CT' :C \ {i) and C=+ =- V (t).
Lemma 4.2. Consider any E (0,1) and laws P+: and Q Let (A,o*)
GBM, (P. Q). Optionally, let y SI(a", SS,")) where E y" is the side informa- tion for any laws (S+,S_) y. Then any i E [m]. the genie score for the ith label is given by
P-,P_.0.
No side information:
log (+(()))
Σ log Q(Ais)
+ log
Q(Ayg)
P_ P_(Ai))
1 1-p)
JECT
jEC
Side information:
2
Σ log jECT
(+((Ai)) @(Atg)
Σ log
2(Ais) P_((
+log
( P_) (1-p)
+log
S+((s)
S_(1))
jEC
Motivation behind our Spectral Strategy. Due to the independence of A and y, conditioned on a², the genie score = under side information is simply the score without side information with the addition of the log-likelihoon ratio of the node attribute y4. Intuitively, we devise principled method for determining the weights of the cigenvector combination and threshold value in our spec- tral algorithm such that ,th entry of the vector formed approximates the the genie score 2 under no side information. Remarkably, the spectral algorithm will approximate this statistic from eigen- vectors of A, despite not knowing CT.¹ and C=*. In light of Lemma 4.2 it is also immediate to see the motivation behind the use of side information prescribed in ( In particular, the genie scores undergo exactly the same transformation when the side information becomes available according to Lemma 4.2 We derive the closed-form expressions for these additive factors in (T) for our examples of side information channels.

---

Published as a conference paper at ICLR 2025
Lemma 4.3, For any E [n]. the log- log-likelihood ratio of side information label is given by
UV, for v., v- E TR" and o² 0, GF (Gaussian features): When y ~ ,F(a", ,U- -V-,
(+t+
11 -v- v-12
113
11
log
(_()
20²
BEC channel: When y BEC(
eor (0,
+00,
o = +1;
S+(1))
log
(_:))
-00
of = -1;
otherwise.
BSC channel: When y BSC(O* for a E 00,0.5)
S+ (11)
log 1 a
log 8- (3:k)
9i
Genie Success with Margin above the IT Limit: We start by crucial observation about the genie scores, which will be important in analyzing the spectral algorithm. We show that above the informatiin-theerrtic limit, the genie score have the correct sign corresponding but with a sufficient margin. We show the for any model GBM and optionally a side information channel, whenever I" 1, there exists a constant ò such that with high probability
the true label,
min of 2 > 8 llgg n, iE|n]
formalized in Lemma D.I
GENIE TO SPECTRAL ALGORITHM (FOR ROS AND SBM)
In light of Eq. (9) if an algorithm can approximate the genie score up additive error of o(log n), then sign thresholding will correctly recover all the labels. As ROS and SBM entries are from exponential families, the log-likelihood is affine function of the observations Aij. and thus, the genie score vector is an affine function of A. I.e.
Aw" + +y1n (in loo norm),
(10)
for a certain & E R and respectively. See Lemmas F. (ROS) and G.2 (SBM) for precise statements. Note that (w4, w-, are just scalars that can be calculated from the model parameters and do not depend on a². The main power of the genie lies in forming the vector w", which requires knowing the locations C² and C_. Then the question that remains is how one may come up with a proxy for w" without knowing C+ and C__ such that the genie score is well-approximated.
R th with entries (w4, w-) E IR2 in the locations of C+ and C_
Warm-up: Degree Profiling Algorithm for BEC and BSC Channels. Under BEC and BSC channels, a natural question is then what we simply trust the side information labels y (-1,0,+1)" and y E +1}, respectively. In particular, we use the proxy for w" where
w. dp w. [y +1] + w- 1 [y: -1] where just trust the side information on the face
value and use the locations of S_ == {i [n] y: = +1) and S_ == E [n] y = -1) instead
(i
of C. and C_.
is known that the asymptotic tooommation-theorttie threshold does not shift for the BEC and BSC O(n and a O(n *) for some 8 0 (Dreveton et al. 2024 Saad & Nosratinia 2018). Therefore, the side information y already satisfies almost exact recovery criterion, recovering (1 o(1) labels correctly. Hence, we have C.A5,,,ICC |C-As_ = o(n) with high probability. We then show that for this proxy choice of scores 2d, indeed have || 1=dp-="0 =1 ollog n.), and thus, the dlegree-profiling algorithm succeeds down the shifted threshold. The formal theorems and algorithms can be found in Appendix [F3 and G.3
channels unless
Remark 5.1. We emphasize that the degree profiling algorithi has an important caveat that would fail to recover labels exactly from tuple (A,y), when side information strength is "weak"
8

---

Published as a conference paper at ICLR 2025
or completely absent, even though the recovery was possible from A. This is because just using y as a proxy to mimic the genie is detrimental if the primary signal is present in A. To overcome this, one has to get preliminary almost exactly correct labels utilizing A, and then mimic the genie using this prelininary labeling as proxy. This exactly corresponds to the two-stage strategies described in Appendix AA.] Remarkably, our spectral algorithm in just one stage recovers all the labels correctly from (A, y) (including no side information), whenever it is possible to do so, and that too for any side information channel.
5.1 SPECTRAL ALGORITIIM
Spectral Algorithm. The spectral algorithm primarily uses the signal from eigenvectors of A to approximate 2", rather than relying on side information. Therefore, the spectral algorithm affords significantly more versatility than the degree-profiling algorithm, and succeeds without any clean-up step with more general or even no side information. The design of our spectral algorithm is informed by the entrywise eigenvector analysis result of Abbe et al. 2020), which allows to say that the leading K eigenvectors of A satisfy
Aut X;
RJ
(11)
where (Ai, uu) is the corresponding eigenvector of the expectation matrix B[A o²), and the ap- proximation is in the lor norm. Here K = 1 for ROS and K 2 for SBM. For both models, the matrix E[A | o²] has a "block" structure, so do its top eigenvectors as well. Thus, we can find an appropriate linear combination coefficients (c))εE[K] such that the optimal genie combination vector
K
w
(12)
is important to note that computing (c:)vE(K) does not require knowing the ground-truth o". This is because the block structure wn and {u; HE([K] align leaving the coefficients always the same.
Algorithm An informal sketch of the spectral algorithm
Input: An observation matrix A R and the model parameter Optionally, the side informa- tion E yd and the associated parameters.
Output: An estimate of community assignments öspec-
1: Compute coefficients (c))E(k) from the model parameters such that w² se Eie u
2: Compute the top K eigenpairs of A denoted by (u, Ax).
3: Form the spectral score vector:
No side information:
K
9000 1,, +
Σ u.a.
Side information: If side information is present, further update
S+ S (1)
spec
spec
+ log
4: Sppc = (gn
Then the spectral score vector, when the side information is absent, is given by
K
Au
10
Spcc 11n
C:
>1,
Aw"
1=1
This achieves an Lo approximation of the genie score under no side information using eigenvectors of When side information is present, due to Lemma 4.2 , it suffices to add the log-likelihood ratio vector from (T) The approximations are tight enough such that we achieve
2 =" Il = o(logn)
As common in the exact recovery literature, we assume that model parameters are already given. In Remark A. we discuss how to estimate them if they are unknown, and in what cases the spectral algorithm robust enough continue succeed when we use these estimates as proxies.

---

Published as a conference paper at ICLR 2025
Recalling that the genie scores succeed with a margin of (llogn) by (9) above the IT threshold immediately gives us the optimality of the spectral algorithm.
Remark 5.2. We remark that, to show the impossibility of recovery, due to the optimality of MAP, Dreveton al. (2024) shows that the MAP estimator (Definition 2.9) fails below the threshold. However, their proof indeed shows an even stronger statement that below the threshold, even the genie-aided estimators ( fail, Both their impossibility and our achievability of spectral algorithm results are driven by the genie-aided estimators, so comes threshold collapse: the genie-aided estimators, spectral estimator, and MAP estimator all achieve the same recovery threshold. The entire discussion can be summarized in Figure
surprise that there is certain
1. Genie scores succeed with [llgg n) margin
(a)
(b)
(c)
4. For all i [n] Tgen. succeeds
Spec succeeds
GHA succedds
Figure 3: Summary our unified proof framework. Our spectral algorithm is designed such that (a) holds. Note that: (b) follows from the optimality of MMP and (c) follows from Lemma 4.1 Finally, we get the threshold collapse phenomenon because below the IT threshold, the event in the fourth block happens with probability (1), and above the IT threshold, the event in the first block happens with high probability (
Remark 5.3 (Runtime). Our spectral algorithm has nearly linear runtime in the input size (# of non-zero entries of A). That is for SBM and ROS, runtime Ó(n) (due to a sparse network) and Ó(n²) respectively. The implementation details are already laid out in (Gaudio & Joshi 2023 Section 4) and (Dhara al. 2022b Remark 2.1); the idea is to compute top eigenpairs sequen- tially using the faster eigenvector computation Garber et al. (2016). The use of side information requires only (n)) additional computation.
DISCUSSION AND FUTURE WORK
In this paper, we provide a systematic treatment of designing optimal spectral algorithms for two- community matrix inference problems under side information, focused on the Bernoulli and Gaus- sian cases. From a technical standpoint, our work makes rigorous connection between spectral algorithms and genie-aided estimators, characterizing their effectiveness in achieving sharp thresh- olds for various exact recovery problems in recent line of work. We refer the reader Appendix A.2 for detailed discussion on this. Understanding the capabilities of such vanilla spectral algo- rithms, without any clean-up stage, is of fundamental interest; we hope this perspective will guide the design and analysis of spectral algorithms for exact community recovery problems moving for- ward. Some directions for future work include:
Exact recovery in Gaussian Mixture Block Model: In a recent work, Li Schramm (2023) proposed an alternative model to better capture real-world networks and sketched out the general landscape for recovery by studying almost exact recovery. What about exact recovery? Interestingly, [i & Schramm (2023) proposed exactly the same vanilla spectral algorithm and showed it achieves almost exact recovery. Does it also succeed for exact recovery?
More general degree-profiling: A natural analogue of degree- algorithm for more general side information beyond BEC and BSC is to -ggnthreshool the log- ligeeloodoood ra- tio vector log S+ (v) to compute preliminary labeling. We conjecture that whenever such side information is sufficient to shift the exact recovery threshold, the preliminary assignment will already correctly compute (1 ffa)c-fattion of labels. Emulating the genie then using this labeling as proxy should succeed in exact recovery (though with the limitation detailed Remark 5.1).
More general settings: To design spectral algorithms for more than two communities and more general observation distributions (P4, P_, Q) from a class of exponential families (also see details in Appendix A.2
10

---

Published as a conference paper at ICLR 2025
Acknowledgements. J.G. supported in part by NSF CCF-21541O, and N.J. was supported in part by the Institute for Data, Econometric, Algorithms, and Learning (NSF TRIPODS HDR). The authors thank Raghav Sinha from the Illinois Mathematics and Science Academy for preliminary empirical study.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446 65311, 2017.
Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. IEEE Transac- tions on Network Science and Engineering, 1(1):10-22, 2014.
Emmanuel Abbe, Afonso S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62:471-487, 2016.
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of Statistics, 48 3:1452-1474, 2020.
Emmanuel Abbe, Francois Baccelli, and Abishek Sankararaman. Community detection on euclidean random graphs. Information and Inference: A Journal of the IMA, 10(1):109-160, 2021.
Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An bp theory of pea and spectral clustering. The Annals of Statistics, 50(4):2359-25) 2215,, 2022.
Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding large hidden clique in random graph. Random Structures & Algorithms, 13(3-4):457-466, 1998.
Eric Bair. Semi Semi-supervised clustering methods. Wiley Interdisciplinary Reviews: Computational Statistics, 5(5):349-361, 2013.
Ramnath Balasubramanyan and William W Cohen. Block-LDA: Jointly modeling entity- antty-annnotatdd text and entity-entity links. In Proceedings of the 2011 SIAM International Conference on Data Mining, pp. 450-461. SIAM, 2011.
Afonso S Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163:145-167, 2017.
Sugato Basu, Mikhail Bilenko, and Raymond Mooney. A probabilistic framework for semi- supervised clustering. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 59-68, 2004.
Norbert Binkiewicz, Joshua T Vogelstein, and Karl Rohe. Biometrika, 104(2):361-377 2017.
Covariate-assisted spectral clustering.
Cécile Bothorel, Juan David Cruz, Matteo Magnani, and Barbora Micenkova. Clustering attributed graphs: models, measures and methods. Network Science, 3(3):408-444, 2015.
Guillaume Braun, Hemant Tyagi, and Christophe Biemacki.. An iterative clustering algorithm for the contextual stochastic block model with optimality guarantees. In International Conference on Machine Learning, pp. 2257-2291. PMLR, 2022.
Guy Bresler, Chenghao Guo. and Yury Polyanskiy. Thresholds for reconstruction of random hyper- graphs from graph projections. In The Thirty Seventh Annual Conference on Learning Theory, pp. 632-647. PMLR, 2024.
T Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Inference via message passing on partially labeled stochastic block models. arXiv preprint arXiv:1603.06923 2016.
Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for submatrix localization in large noisy matrix. The Annals of Statisties, 45(4):1403-1444 2017.
11

---

Published as a conference paper at ICLR 2025
Jonathan Chang and David M Blei. Hierarchical relational models for document networks. The Annals of Applied Statistics, pp. 124-150, 2010.
Olivier Chapelle, Jason Weston, and Bernhard Schölkopf. Cluster kemels for semi-supervised learn- ing. Advances in neural information processing systems, 13, 2002.
Hong Cheng, Yang Zhou, and Jeffrey Xu Yu. Clustering large attributed graphs: A balance be- tween structural and attribute similarities. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(2):1-33, 2011.
Amin Coja-Oghlan. A spectral heuristic for bisecting random graphs. Random Structures & Algo- rithms, 29(3):351-398, 2006.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011.
Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. Strong consistency, graph Laplacians, and the stochastic block model. J. Mach. Learn. Res., 22(117):1-44, 2021.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 2018.
Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon. Spectral recovery of binary censored block models. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3389-3416 SIAM, 2022a.
Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon. Spectral algorithms optimally recover (censored) planted dense subgraphs. arXiv preprint arXiv:2203. 11847, 2022b.
Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon. The power of two matrices in spectral algorithms for community recovery. IEEE Transactions Information Theory, 2023.
Maximilien Dreveton, Felipe Fernandes, and Daniel Figueiredo. Exact recovery and bregman hard clustering of node-attributed stochastic block model. Advances in Neural Information Processing Systems, 36, 2024.
Dan Garber, Elad Hazan, Chi Jin, Cameron Musco, Praneeth Netrapalli, Aaron Sidford, et al. Faster eigenvector computation via shift-and-invert preconditioning. International Conference on Machine Learning, pp. 2626-26666 2634. PMLR, 2016.
Julia Gaudio and Nirmit Joshi. Community detection in the hypergraph SBM: Exact recovery given the similarity matrix. In The Thirty Sixth Annual Conference on Learning Theory, pp. 469-510. PMLR, 2023.
Julia Gaudio and Heming Liu. arXiv:2408. 13075, 2024.
Spectral recovery in the labeled sbm.
arXiv preprint
Julia Gaudio, Miklos Z Racz, and Anirudh Sridhar, Exact community recovery in correlated stochas- tic block models. In Conference Learning Theory, pp. 2183-2241. PMLR, 2022.
Julia Gaudio, Charlie Guan, Xiaochun Niu, and Ermin Wei. Exact label recovery euclidean random graphs. arXiv preprint arXiv:2407.11166 2024a.
Julia Gaudio, Xiaochun Niu, and Ermin Wei. Exact community recovery in the geometric sbm. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 2158-211 2184. SIAM, 2024b.
Jaume Gibert, Emnest Valveny, and Horst Bunke. Graph embedding in vector spaces by node attribute statisties. Pattern Recognition, 45(9):3072-3083, 2012.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used uni- variate continuous distributions. Information Sciences, 249: 124-131, 2013.
12

---

Published as a conference paper at ICLR 2025
Stephan Günnemann, Ines Färber, Sebastian Raubach, and Thomas Seidl. Spectral subspace cluster- ing for graphs with feature vectors. In 2013 IEEE 13th International Conference on Data Mining, pp. 231-240. IEEE, 2013.
Bruce Hajek, Yihong Wu, and Jiaming Xu. Exact recovery threshold in the binary censored block model. In 2015 IEEE Information Theory Workshop-Fall (ITW), pp- 99-103. IEFF, 2015.
Bruce Hajek, Yihong Wu, and Jiamiig Xu. Achieving exact cluster recovery threshold via semidef- inite programming. IEEE Transactions Information Theory, 62(5):2788-2797, 2016.
Bruce Hajek, Yihong Wu, and Jiaming Xu. Submatrix localization via message passing. Journal of Machine Learning Research, 18(186):152,, 2018.
Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi. Phase transitions in semidefinite relaxations. Proceedings of the National Academy of Sciences, 113(16):E2218 E2211-E23221 2016.
Yicong Jiang and Tracy Ke. Semi-supervised community detection via structural similarity metrics. In The Eleventh International Conference on Learning Representations, 2023.
Arun Kadavankandy, Konstantin Avrachenkov, Laura Cottatellucci, and Rajesh Sundaresan. The power of side-information in subgraph detection. IEFE Transactions on Signal Processing, 66 (7)11905-1919 2017.
Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and local information clustering labeled block models. IEEE Transactions on Information Theory, 62(10):5906-5517, 2010 2016.
Anastasia Krithara, Massih Amini, Jean-Michel Renders, and Cyril Goutte. Semi-supervised document classification with mislabeling error model. In Advances in Information Retrieval: 30th European Conference on IR Research, ECIR 2008, Glasgow, UK, March 30-April 3, 2008, Proceedings 30, pp. 370-381. Springer, 2008.
Shuangping Li and Tselil Schramm. Spectral clustering in the gaussian mixture block model. arXiv preprint arXiv:2305.0099 2023.
Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 529-537 IEBE, 2001.
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques algorithms and data analysis. Cambridge university press, 2017.
Javad Zahedi Moghaddam, Mohammad Esmacili, and Aria Nosratinia. Exact recovery threshold in dynamic binary censored block model. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 1088-1093. IEEE, 2022.
Elchanan Mossel and Jiaming Xu. Local algorithms for block models with side information. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp- 71 71-80, 2016.
Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. In Proceedings of the ferty-seventh annual ACM symposium on Theory of computing, pp. 69-75, 2015.
Mark EJ Newman and Aaron Clauset. Structure and inference in annotated networks. Nature communications, 11863, 2016.
Li Ni, Junnan Ge, Yiwen Zhang, Wenjian Luo, and Victor Sheng. Semi-supervised local commu- nity detection. IEEE Transactions Knowledge and Data Engineering, 36(2):823 839, 2024. doi: 10.11099TKDDE
Miklos Racz and Anirudh Sridhar. Correlated stochastic block models: Exact graph matching with applications to recovering communities. Advances in Neural Information Processing Systems, 34: 12259-22273 2021.
13

---

Published as a conference paper at ICLR 2025
Hussein Saad and Aria Nosratinia. Community detection with side information: Exact recovery under the stochastic block model. IEEE Journal of Selected Topics in Signal Processing, 12(5): 944-958, 2018.
Hussein Saad and Aria Nosratinia. Recovering single community with side information. IEEE Transactions on Information Theory, 66(12))793--796, 2020.
Jesper E Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine Learn- ing, 109(2):373 440, 2020.
Van Vu. A simple svd algorithm for finding hidden partitions. Combinatorics, Probability and Computing, 27(1):124- 140, 2018.
Xixi Wu, Yun Xiong, Yao Zhang, Yizhu Jiao, Caihua Shan, Yiheng Sun, Yangyong Zhu, and Philip Yu. Clare: A semi-supervised community detection algorithm. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pp. 2059-2069, 2022.
Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. model-based approach to
attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD international conference on management of data, pp. 505-516, 2012.
Jaewon Yang, Julian McAuley, and Jure Leskovec. Community detection in networks with node attributes. In 2013 IEEE 13th international conference data mining, pp. 1151-1156. IEEE, 2013.
Tianbao Yang, Rong Jin, Yun Chi, and Shenghuo Zhu. Combining link and content for community detection: discriminative approach. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 927-936, 2009.
Se-Young Yun and Alexandre Proutiere. Accurate community detection in the stochastic block model via spectral algorithms. arXiv preprint urXiv:1412.735.. 2014.
Se- Youn Yun and Alexandre Proutiere. Optimal cluster recovery in the labeled stochastic block model. Advances in Neural Information Processing Systems, 29, 2016.
Hugo Zanghi, Stevenn Volant, and Christophe Ambroise. Clustering based on random graph model embedding vertex features. Pattern Recognition Letters, 31 31(9):30-836, 2010.
Ning Zhang, Weina Wang, and Lele Wang. Attributed graph alignment. In 202/ IEEE International Symposium on Information Theory (ISIT), pp. 1829-1834. IEFF, 2021.
Pan Zhang, Cristopher Moore, and Lenka Zdeborová. Phase transitions in semisupervised clustering of sparse networks. Physical Review E, 90(5):052802, 2014.
Yuan Zhang, Elizaveta Levina, and Ji Zhu. Community detection in networks with node features. Electronic Journal of Statistics, 10:3153-3178 2016.
Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. Graph clustering based on structural/atrribuee similar- ities. Proceedings of the VLDB Endowment, 2(1):718-729 2009.
14

---

Published as a conference paper at ICLR 2025
Appendices
Deferred Discussions
16
A.1
Additional Simulations and Interpreting Information Theoretic Limits
16
A.2
Future Extensions and Prior Works and on Spectral Algorithms
18
Additional Related Work
19
A.4
Proof Review of Dreveton et al. (2024) for Proposition 2.10
20
Notation and Probability Facts
20
B. I Notation
20
B.2 Standard Probability Lemmas
Verification for Information Theoretic Limits
21
D Omitted Proofs from 4
23
D.1 Genie Success with Margin above the Threshold.
25
Entrywise Behavior of Eigenvectors,
27
E.1
Entrywise Analysis for Eigenvectors for ROS.
27
E.2
Entrywise Analysis of Eigenvectors for SBM
F
Proofs and Algorithms for ROS,
31
Genie scores' formula when no side information
................................
F2
Spectral Algorithm and Proof of Theorem
................................
33
Degree-Profiline Algorithm for BEC and BSC Channels
................................
35
Proofs and Algorithms for SBM.
39
Genie scores' formula when no side information)
39
G.2
Spectral Algorithm and Proof of Theorem
G.3
Algorithm for BEC and BSC Channels
44
15

---

Published as a conference paper at ICLR 2025
A DEFERRED DISCUSSIONS
Remark A.1 (Estimating Model Parameters when Unknown). In our spectral algorithm design, we assumed that the model parameters are already given as the input. If the distribution parameters for P+, P-, and Q are unknown, one can perform almost exact recovery to find preliminary labeling and the preliminary labeling to estimate the distributional parameters. One can then use these estimates as a proxy in the spectral algorithm or even. As result, the practical advantage of the spectral algorithm over two-stage approaches is not clear if the model parameters are not known, however, the spectral algorithm's analysis has still been of great interest due to its elegance and for theoretical investigations. The plug-in estimates created this way for SBM and ROS parameters suffice for the spectral algorithm to continue to succeed. We can estimate the parameters for S. and S_ similarly from preliminary labelings if they are parameterized distributions like BEC, BSC, GF However, whether the estimates would be good enough for the spectral algorithu continue to succeed depends on the channel. For our examples:
GF: the estimated means from preliminary labelings suffice for the spectral algorithm to continue to work.
BEC: the algorithm does not use E to compute log need to estimate.
S= S- (v)) (Lemma 4.3), so there is no
BSC: it remains unclear whether the estimated would be good enough.
Remark A.2 (Zz=synchronization as rescaled ROS). We remark that the Zz-symnchronzzation prob- lem is rypically formulated as Aij x;2; + oWij- where x² is an unknown vector is chosen uniformly at random from the [+1] W is zero-diagonal symmetric matrix with independent entries sampled from (0, 1) (Bandeira et al. 2017]. In that case, the relevant parametrization of
is σ = = log n. as v 21og
n is the threshold value for exact recovery Bandeira et al. (017))
Thus, taking = 1/ve, b- -1 1/ and = 1/2 in our ROS model (Definition 2.2 produces matrix A such that
log n
Ag
2 + WW x² (Onifom((=1]+)
After scaling A by ev/ ////og n, we achieve the standard model x² xx" oW (with zero diagonal).
A.1 ADDITIONAL SIMULATIONS AND INTERPRETING INFORMATION THEORETIC LIMITS
Empirical Validations. In Figure 2 we consider the Zz-Synchronizztioon setting, which corre- sponds to ROS a. b) for b a and م 1/2. We considered our three examples of side information whose parameters are further parameterized by strength parameter | 2 0.
Gaussian Features (Definition 2.5
We consider
1 and 24 = Byloog E and
= -B E R. BEC Channel (Definition
2.6
: We set = -2
BSC Channel (Definition
2.7 We set a = 1/ + 1) O(n
In addition to Sz-Synchronization (Gaussian edge observations), we also verify that the spectral algorithm achieves the information-therret. limits under side information also for Bernoulli edge observations (Theorem 2) In particular, we will consider Symmetric SBM for which 01 dg and - = 1/ / in Definition 2.3 As there are now more than two parameters (a, b, and side informa- tion), we fix the side information strength parameter 3 and vary (a, b). See Figures 4 and 5 for BEC and BSC channels respectively.
Symmetric SBM Threshold. is given by
In this case, as we shall derive in Lemma C.6 the function L()) in
1 (a b a'bi-t b²att1).
L(t) 2 The function L(t) has the unique minimizer at t* 1/2.
I sup L(t)= (Va- vb)2 1E(1.1)
16

---

Published as a conference paper at ICLR 2025
Symnerric
Flaaatr Choool
3- Interdtt Chareel
(a) 0.5
3 0.7
Figure 4: (BEC Channel). For the symmetric SBM, i.e. SBM. (1/2, a, b). We let n 300 and consider the BEC side information channel with - for / E f0, 0.7) Figures 4a and 4b respectively. We nun the spectral algorithm (Algorithm 3 over 50 independent trials and plot its success rate for the exact recovery. Lighter pixels correspond to higher probability of success. Finally, the blue and red curves are the theoretical information-theoreti thresholds.
Spmmettic BESE wilh BSC Clasael Eoe d- 3.5
Spanckii: SE3 with BSC Casanei for 007
5ie Fmraee Chonnel
BSC Charael
(a) 0 = 0.5
(b) 3 = 0.7
Figure (BSC Channel). The setup identical the one in Figure but now with the BSC channel with flipping prohability a 1/(n + 1) = On for 3 E (0,5,0.7).
This the well-known cetmmattion-hhooeetti for the symmetric SBM (Abbe 2017 Abbe et al., 2016), which can be interpreted signal strength.
Rank One Spike Threshold. For ROS(p, a, b) (Definition 2.2 us define
V == (p, (a b) (1 p))²).
This quantity V can be interpreted as the signal-to-noise ratio, and controls the information-theoretic limit ROS(p, a, b). In particular, in the absence side information, we have:
L(l) = t(1-t) - t) (p, a, b), and thus, 1" sup L(() (p,.,, 10(1.1
2
8
Side Information. the presence of side information, the function L(t) shifts by a function of
t due additive term Dr I from B). The final limits I" then calculated by taking the supre(o.1) and thus, they do not necessarily have simple closed-form expressions. However, the additive shifts before taking the supremum have simplified expressions which we specify for each of the three channels.
17

---

Published as a conference paper at ICLR 2025
Gaussian Features (Definition 2.5 In GF with V4 B Vlg and e_ B_ =0glog
LGF (1) = sI)) + t(1 t) || 104--33116 3_112
2x²
See Lemma C.2 for the derivation. The shifts depends on the signal strength of side infor-
mation
|
BEC Channel (Definition 2.6
When c = ( for a parameter 2 0, we have LBEC(t) = (t)- + 3. The signal strength 3 determines the shift.
See Lemma
C.3
BSC Channel (Definition
2.7 When (n= for signal strength parameter / 2 0,
by Lemma
C.4 we have
ABsc(() Tno st + 8 min -t--
In Figure 6 we compare the final IT thresholds for BEC and BSC channels against the threshold without side information for ROS.
Possible without needing any side information Trivial just based on side information
Possible using either BEC or BSC but not otherwise
Possible using BEC but not with BSC Impossible despite BEC BSC side information
Figure Visualization of Information Theoretic Thresholds for ROS. The colored regions in the above VP vs 9 plot indicate how BEC or BSC side information of strength helps.
A.2 FUTURE EXTENSIONS AND PRIOR WORKS AND ON SPECTRAL ALGORITIMS
Future Extensions. We now describe, how we can generalize the spectral algorithm to more than two communities and more general distribution families. The entire genie-aided framework general- izes to the K K-community case where each vertex now has K score values {2) k [K] [n]]. The score for the thth community for the vertex is
2i,00) log P(a = A.y,o",)).
The optimal genie-based estimator then simply given by HG = arg max =[,()) Mimicking the genie, the spectral algorithm now also computes K different score vectors to approximate the statisties of the genie scores and takes the entrywise arg max come up with the spectral estimator of the labeling.
We note that the entrywise eigenvectors behaviors of Abbe al. 2020 for top eigenvectors continue to hold. Despite this, (Abbe et al.] 2020 Appendix C.4) noted difficulties in designing spectral algorithms for more than two blocks due to the multiplicity eigenvalues and eigenvectors being only computed up to rotation. But note that, except for these degenerate cases (some measure zero subset of parameters where exact recovery is possible), the algorithm should able to emulate the genie-aides aided estimation and achieve optimality. It remains an interesting open question to handle these degenerate cases by a spectral strategy, which may require new ideas.
We expect that more general distribution families for pairwise observation matrix could be possible to handle. In particular, we first summarize the key technical properties we relied on for designing the spectral algorithms for ROS and SBM.
18

---

Published as a conference paper at ICLR 2025
1. The genie-score vector takes special form where it is affine function of the entries of the matrices.
Aw" + 7y1n.
2. The optimal genie linear combination vector w" is in the span of eigenvectors of EE(A o*)-
3. Lastly, the eigenvector of A, and its corresponding eigenvector u' of B[A] o²). by Abbe et al. (0166) we have
Au
which allows us to emulate the genie using eigenvectors of A.
Property/ I holds more generally for any exponential family of distributions. The linear combinations in Property 2 needs to be designed for specific distribution families, but we expect this to be possible in great generality due to the block structure of the expectation matrices. Finally, one needs to verify the entrywise behavior of eigenvector A holds. Abbe et al. has general conditions under which this behavior holds, however, verifying the technical conditions for the distribution families remains to be the main challenge.
Prior Works. We note that prior works spectral algorithms mentioned in Section I are all essentially emulating the genie, and the models satisfy the aforementioned three properties. For example, prior works have used weighted adjacency matrices (Dhara et al. (022a), and even mul- tiple adjacency matrices (Dhara et al., 2023 Gaudio & Liu 2024) in order to bring out "helpful" eigenvectors that can be used to mimic the genic estimators.
Interestingly, for the exact recovery problem in the hypergraph SBM from the similarity matrix W (counting the hyperedges involving each pair of vertices), Gaudio & Joshi (2023) devised the same spectral strategy of computing the signs of the second eigenvector in the symmetric case and analyzed by proving the Lo behavior of eigenvectors. However, this strategy is known to be strictly suboptimal (Bresler et al., (024) for this setting. This is because the genie scores are not affine functions of the entries of the matrices W due to internal dependencies. However, it is interesting to note that the algorithm achieves the threshold of the min-bisectio estimator (also not efficiently computable), which is the first order (linear) approximation of MAP, In other words, the eigenvector approximated the statistics that correspond to the linear terms of the genie scores. This suggests that even when the likelihood not a linear function of the entries of the observation matrix, while the spectral algorithm may be suboptimal, using our framework it could still be possible to get non-trivial performance guarantce.
A.3 ADDITIONAL RELATED WORK
Local to global amplification and two stage algorithms. The SBM is known exhibit local- to-global amplification, in the sense that whenever (local) recovery of single vertex label given the labels of all other vertices is possible with probability
o (1/n). then (global) exact recovery
is possible with probability - o(1) (see e.g.. Abbe (2017) ). Two-stage algorithms, which are
prevalent in the literature (Abbe et al. 2016, Coja- jigla- 2006 Vul (0188] Yun & Proutiere 2014]
2016 Gaudio et al., 2024a), essentially leverage this statistical property.
Community recovery under side information. Community detection problems with side infor- mation have been studied in numerous settings. Saad and Nosratinia Saad & Nosratinia (2018) considered exact recovery in the symmetric, balanced SBM, under the BEC, BSC, and more general side information with K features, where K may grow with n. Additionally, an efficient two-stage exact recovery algorithm was proposed. Vector-valued side information was also studied in [Sadd & Nosratinial (2020), in the recovery of planted dense subgraph of size o(n). Community detec- tion in the sparse setting under side information has received significant attention- see for example Mossel & Xu (2016): Cai al. (2016); Kadavankandy et al. (2017); Kanade et al. (2016); Desh- pande et al. (2018); Braun et al. (2022); we note that Deshpande et al. (2018) considers Gaussian side information with either Bernoulli or Gaussian pairwise observations. See also Zhang et al.
(2014) which includes statistical physics conjectures for recovery thresholds derived from the cavity method. Numerous approaches for clustering have been proposed in the network science literature, such Newman & Clauset (2016); Zanghi et al. (2010); Yang al. (2009); Xu al. (2012) Yang cet al. (2013); Zhang et al. (2016); Gibert et al. (20122012)) Zhou et al. (2009); Günnemann et al. (013);
Cheng et al. 2011 Binkiewicz al. 2017); see Bothorel et al. 20155) for survey.
19

---

Published as a conference paper at ICLR 2025
Other inference problems with side information Related problems in the literature include doc- ument classification Krithara et al. (2008); Chang & Blei (2010) and text classification Balasubra- manyan & Cohen (2011). A recent line of work studies the problem of community detection from
correlated graphs Racz & Sridhar ; Gaudio et al.] (2022), so that the additional graph plays the role of side information. See also Zhang et al.] (202T). which considers attributed graph alignment. More broadly, inference with side information falls under the area of semi-supervised learning (see
e.g. Van Engelen & Hoos
2020): Chapelle et al. (2002); Bair 2013): Basu et al. (2004);
Newman
& Clauset (0116))
A.4 PROOF REVIEW OF DREVETON ET AL. 2024) FOR PROPOSITION 2.10
We first argue that the impossibility result in Proposition 2.10 is just a special case of the correspond- ing result in (Dreveton et al. ( (Theorem 1]. Note that we have only one pair of communities (C+,C_), which is responsible for determining the threshold. Exactly as in Dreveton et al. (2024). we require the limit (tt) = lim logn C+, -) to exist and be strictly concave.
For the MAP's success, we note that the only change is that we relax the requirement in two ways: (i) we do not require [tt) is strictly concave, (ii) we do not require that [(t)) always exists, and are fine when the limit does not exist while diverging to +.0. Dreveton et al.) prove the MAP success in two parts, by first bounding the probability of the event that an assignment vector a with hamming distance of m has higher likelihood than the ground truth o* (see their Lemma 3). In the second step (see their Appendix A.4), they do a union bound argument over all such possible vectors with the Hamming distance of m, and all varying 1 S S n/2.
We first note that that their Lemma 3 statement as well as its proof do not make use of the condition that L(t) is strictly concave. In Appendix A.4, the union bound argument also does not require L(t) is strictly concave (it only uses suprero.1) L(t) > 1), and the strict concavity was only required to show the impossibility direction. To justify the second relaxation where we allow the cases of infinite limit Lt),, we first note that their Lemma 3 is non-asymptotic anyway and derived for any finite n. Later, in Appendix A.4, we observe that the existence of the constants c > 0 and λ > 0 holds true, even when the limit L(t) +oo. In partieular, the purpose behind the requirement was to exclude the cases when L(t) does not converge but neither approaches +00.
B NOTATION AND PROBABILITY FACTS
B.1 NOTATION
Throughout the paper, we extensively use the standard extended real line algebra on IR := R U 0,00+00) where +o0 and - -oo are respectively greater and less than any other real number. Moreover, for any two a, b E R. we will define - 0 when b. We also view log : R2 IR where log(0) = -o0 and log(+0o) = +oc, and use Olog 0 = 0 Olog( +oo) = 0, following the convention in the information-theory literature.
For any two vectors of random variables X and Y. we write X 1 Y if entries of one are independent from the others. For any real numbers a, b R, denote aVb = max(a, (a, b} and aAb min(a, b). Let sgn RR- + {11 be the function defined by sgn(r) 1 if x 2 0 and sgn(x) = - if æ < 0. We also extend the definition to vectors; let sgn R" - {+ ) be the map defined by applying the sign function componentwise. We define R,
o0). For E N. we write [n] = 21. n). We use the standard notation o(.), O(.), (.), 2(.), O(.) etc. throughout the paper. For non-negative sequences (22) and (In)n2 we write an S bn to mean an S Cb,, for some constant C' > O.
The notation x is similar, hiding two constants in upper and lower bounds. Moreover, we denote a, R 6n shorthand for lim, bn = 1.
For a vector x E R", we define ||I||| = (E 2?)1/3 -= (aal, and || = max; | Additionally, for any E [n]. we define r= as the vector in R" such that (x-i); xy for + and (x=-);; 0. For any matrix M E Raxx_ Mj refers its 7th row, which is row vector, and M, refers to its ęth column, which is a column vector. The matrix spectral norm is [|M]],
supi|al,= || || the matrix + oo norm is 12 sup || = sup, ||
Let zd : x + Rax= be the zero-diagonal mapping, where for any A E Rax* zd(A) = Ag if i f and 0 otherwise.
20

---

Published as a conference paper at ICLR 2025
B.2 STANDARD PROBABILITY LEMMAS
Lemma B.1 (Rényi Divergence Formula). For any two probability laws (A, (), either both discrete or continuous, we have that
)
A(x)
((-1))((A11)) E
B(x)
Proof. The proof is immediate by rearranging the terms from the definition in (4)
Lemma B.2. Les Z ~ ~N(0,,) 1). The for any > O,
(:
1
12 P(Z <
12/2
2
tv2T
We next show that the sampling procedure of the community assignment vector o² in any of the models leads to communities with roughly p and (1 p) fraction of vertices.
Lemma B.3. Let o² E {+1}" n be vector whose coordinates are ii.. with PP = +1) = p- Then, let C+ (i: of = +1} and C_ = {i: of = -1]. Define the event as follow.
E [||C+| pr] 2/3 and ||C_| (1 - p)m| S 2/3/
(13)
Then P(E) 2 1 1 (1).
Proof. For each S i < n, since P(o i.i.d., we have that |C Ki o +1 fol- lows Bin(n, p). The Chernoff bound for binomial random variables (Mitzenmacher & Upfal 2017 Theorem 4.4, Theorem 4.5) implies that for any E (0,
E P([[C+| - 1|| s dn) 2 exp E C=133)
Note that B[[C+]] pn. Choosing 8 pm o(1) (as p 0 is a constant)
P(||C+| - pm| S pm 2/3 2 exp -n
2/3 p² ///33)
2exp (-p2n
Since 1/3 wlog n) and p > 0 is constant,
IP (1 11/3) pm |C+1 $
1/3) pr) 2 000x0eee11100g////333 =
O(n 3)
which implies the lemma.
C VERIFICATION FOR INFORMATION THEORETIC LIMITS
In this section, we will verify the function L(L) is well defined and is strictly concave for both ROS and SBM and in the cases of no side information, or the special cases of GF, BEC and BSC side information channels. As result, even I' well-defined for these settings and sharply characterizes the information-theoreee Theorem 2 optimal, when combined with the impossibility direction of Proposition 2.10 In order to verify these technical conditions, we will use well-established closed form expression of Rényi divergence two Gaussian random variables, e.g. see Gil et al. (003)).
limits in these settings, making our spectral algorithms in Theorem 1 and
Lemma C.1. Let A = ((1, o²
o²La) La) and B N(22, o² 22 for μl, #2 Rd and o² 0. then
t Dx(A]))) = 20 | 12l12
Side Information Terms. We start by analyzing the additive terms that come in L(t) due to the presence of each example of side information channels.
Lemma C.2. Consider the side information laws S+ =N d2 and S_ (V La)
constant o² > 0 and V4 = =B =3olo n and v_ = B_ B B_ E Rd Then
(1 (1- De(S+11S_) t(1 t) B B
lim 000 log
20
which is well-defined Note that this as a function of E (0, 1) is strictly concave when 3+ + B_ it is otherwise.
21

---

Published as a conference paper at ICLR 2025
Proof. The lemma follows from straightforward simplification and the of Lemma C.1
n (1- - t) D.(+
(1 t) t 1|0+
lim n-+00
= lim n-+00
log
log
202
((1 - 1) |13 -3- -3118
log
log n lim n-+00
20²
t(1 t) || 3_112
2x²
Lemma C.3. Consider the side information laws S-) as in the BEC channel with e such that
lim
log(1/e) for 3 2 0, i.e. n -B+((1) Then
log
(1 1- (7((+118-)) 3.
lim x
log
Proof. By definition of Rényi divergence in
(1-() (((+1((_))
(1 (1-1) 1) 1
S+ (+ 2 (_1i))
lim 12-+00
lim
log E.
log n
n
1-0000 log n (t 1)
vims-
log
log(1/c)
lim
lim
B.
m-000
log n
log
Lemma C.4. Consider the side information laws (S+.S-) as in the BSC channel with a such that for 3 2 0, i.e. a = n (++((1) Then
log( (-))
limn-+00
loga
t) (1 (1-t)
lim n. 10000
(5 = B min(l, -1.-
log n
n
Note that this is a concave function of t E 10.
Proof. By definition of Rényi divergence in
lim (1- t) D.(S )|S_) n logn (t (t-1) w:
lim (1- t)
S+ (141) 8- (31)
log E
log n
log(a' (1 a) 1- a 1-1 (1 xx)
lim
n=000
log n
min (Bt ft t)} logn 3.33mi min(l, (}.
lim
log
Deriving Threshold for ROS and SBM Finally, we will derive the expression of L(t) and show that it is strictly concave.
Lemma C.5. Fix E (0, 1) and a, b E IR such that max{[a], [6|} > 0. Consider the distribution (P+,P_, as defined in the ROS model (Definition) 2.2 Then the absence of side information, L(t) is well-defined and given by
L(I) 1(1 (111) (a 6) (pa² + (1 (1-
Moreover, L(t) is strictly concave. Additionally, under GF, BEC, BSC channels described Lem-
mas C.2 C.3 and C.4 respectively, T.(l) continues be well-defined and strictly concave.
22

---

Published as a conference paper at ICLR 2025
Proof. In the absence of side information
[(t) = lim
n
CH2 (+, -) = lim
n11 -6) t)
(pDx(P+1()) + +1 - (1-p)D((1PP))
n=000
log n2
n-000
logn
n(1-t) t)
P. t(a² ab)² logn
t(ab - b2)2 log m
lim 700
+ (1 - p)-
log n
2
n
2
n
(using Lemma B.1
=t(1 t) (pla² ab)²
+ (1 (ab )2) t(1 - (a b) (pa? + (1 - pp]b²)
2
2
Note that when max [a]. [ [b} > 0, the multiplicative coefficient of t( t) is positive. Therefore, L(t) is strictly concave function in (0, 1).
Under side information. L(t) is given by adding another term based on the channel as derived in
Lemmas C.2
C.3 and C.4 Therefore, L(t) continues to be well-defined. Moreover, L(t) still
remains strictly concave because the addition of strictly concave function with another concave function (including just constant) is strictly concave.
O
Lemma C.6. Fix p (0, 1) and 01, a2, b > O. Consider the distribution (P+. Q) defined in the SBM model (Definition 2.3). Then in the absence of side information, L(t) is well-defined and given by
L(t) = tpar + (1 - t)pb + + p)b (1 t) - ppa0- - pa.b--t (1 p)b'a a²-
Moreover, except the degenerate case 01 02 b, have that L(t) is strictly concave. Addi- tionally, under GF, BEC, BSC channels described in Lemmas C.2 C.3 and C.4 respectiie, L(t) continues to be well-defined and strictly concave.
Proof. This is just special case of the expression derived by (Dreveton et al. but for two communities. Note that L(t) is twice differentiable, and
2024 Example 1)
(t) = - (1) (1
bog - p1-
02
log"
b
<
O,
02
a2
unless 01 = 02 b, and thus, L(t) is strictly concave. Similar Lemma C.5 adding another side information channel-specific term to L(t), derived in Lemmas C.2 C.4 the function L(I) is well-defined and strictly concave.
even for SBM, after
C.3
and
D OMITTED PROOFS FROM SECTION
In this section, prove all the genie-aided estimation related lemmas. We start with the proof of Lemma 4.1, which establishes that the failure of some genie-aided estimator implies that the global MAP estimator also fails.
Proof of Lemma We first consider the case when side information (either BEC or BSC) is provided. Let ST {(A, 7. v) 3i [n] such that dem. fails). Similarly, S2 = {AA, o. 7) GMAP fails}. To show the desired claim, it suffices to show that S C S2.
To this end, fix any instance (A, T. 7) E S₁ of (A, ,))) Then by definition of the failure of the genie-aided estimators give below Equation 77. there exists i E [n] such that
F(a -; A.J. J. -)) > P(o o. A, -.
(14)
We now consider the community assignment vector o' E {+1}" whose labeling agrees with ø except for the 7th label, for which df -, Then
IP(o" - d' A, P(o", = d'=, of = = A,T)
P(o". = o A.D) P(o = of A, u-, -.
-P(o" = - A. () P((o = - A.J.o', = -
=
(as oas 0'; = = but of = -7,)
> P(a = - A,y) P(a" = 7. A, = (using (14)
-P(ot. - =0; A,y)
=P(o- δ A.
(15)
23

---

Published as a conference paper at ICLR 2025
By the definition of the MAP estimator ŌMA arg ma Po o(A,T) # o, which implies (A, 0, 3) E S2.
Finally, we consider the case when there is no side information. Define S₁ and S2 similarly, but after dropping y.
Case P+ # P- or + 1/2. Consider any (A, E S1 and follow exactly the same argument used in in deriving (15) (after dropping the conditioning on y). This will lead to the conclusion that (A, σ) E S2. yielding S C S2.
Case P+ P_ and p 1/2. Consider any (A, St. Follow exactly the same argument in (15) and conclude that PP o' A) > Po A). Additionally, due to the symmetry, IP ग A) Po --===AAAi AA) Combining these two, obtain that MAP & (+a*), which implies MAP fails by Definition 2.8. Conclude (A, (A S2, as desired.
We now derive the expressions for genie scores given by Lemma 4.2 without or with side informa- tion.
We first recall the definition of genie scores from 8 For any E [n]. we do the following analysis in each model of side information.
Proof of Lemma 4.2
No side information:
P(a +1 A, o,0",))
Plo +1) o",
10 +11
2/ = log
= log
Pla = -1 A,
Plo = -1) C(A, lo -1))
P(o = +1) C(A
of = +1,
log
(o is independent of o;))
Plaj -1) L(A of = -
P(ao = +1) [(A, o0 = +1,0";)
log
Pla = -1) C04, o = --,00";)
(the likelihood of all but the 5th row is same conditioned under o"; irrespective of o;)
/ (1-
log
p. II PA())) II 2(A))
II Q(A,) II (Ai))
jECT
jEC
jECT
jEC=
(due to the conditional independence of the entries and the law of GBM)
Σ log (Pt))
Σ log
[(Ar))
log
P
[(Ai;)
(_(s))
1-
JECT
JEC
Side information: Again by
g we have
P(o +1 A, A,3. P(a
P(o: = +1 A, oi,
27 log
llog
A, A,y,
Pla =1 A,yi
(conditioned on a".o we have of y-i)
P(oo +1) L(A, Hi, o-, 1 +1]
= log
P(oo -1) C(A, 02,
0 = =
PP(a" = -1).,(A,A 0_ of = +1) IP(y: |0 =
+1) +1)
log
P(a 11) L(A, 0-, o -1) P(ys of -11)
(conditioned on of have y/i A and yi 1 o².))
P(o = +1 A,o P(y a = +1)
log
P(a = -1 A,o",) P(( 0 = =
P(o = +1 A,o
Ply: o = +1)
log
+ log
(16)
P(oo = - A,o2,)
Ply: of -1)
24

---

Published as a conference paper at ICLR 2025
Note that
P(us of - P(ys of = -11
log S+
log
S_ (v:)
Substituting this in (16) along with the definition of genie score without side information using the expression from the case without side information, we obtain
g
and
(P+(As) ((Aig)
2(Aig) PA(g))
+ log ( P
(+ S (-(1))
Σ log JECT
+
Σ log
+ log
JEC
We now show the proof of Lemma tive factor under side information for the special cases of Gaussian Features (GF), Binary Erasure Channel (BEC), and Binary Symmetric Channel (BSC).
4.3
where we explicitly derive the closed form of the addi-
Proof of Lemma 4.3
We break into cases.
Gaussian Features (GF):
1 2
S+ (2:)
| U- 112 - 113/ 11
log
(8
log
- 20
log
exp
20
11
V_
1/
1191
202
Binary Erasure Channel (BEC): If = O. then S+ = S_ (V:) = c. If y: +1,
then (y:) = 1 -e e but S_ (y:) = O, and similarly, 1/s = -1, then S+, (3:) = but
S_ (1)) 1
+00,
if of +1;
S- (w:)
log
(w:)
oc,
if o = --1; otherwise.
0,
Binary Symmetric Channel (BSC):
(+i)
S+
1 a
) 1 1l: +1]+log
(
1 )a) 1 -1] log (1-a)
log
S_ (y()
loog
yi
a
a
D.1 GENIE SUCCESS WITH MARGIN ABOVE THE IT THRESHOLD.
We now give a formal version of the claim that above the informition-thherrtic limit, all the genie scores succeed with margin of 2(lo n)., formalized in the following lemma.
Lemma D.I. Fix P (0, 1) and consider probability laws (P+,P-, Q). Let (A,o") GBM (p.
Q) and we observe A. Condition on o² such that the event E from (13) holds. Optionally, for side information laws S-), we observe y ~ Sl(a" SS,,S_). Let z* be the genie score vector for the corresponding model given by (8). Let I* be defined according to (6). Then if I' then there exists some constant 5 such that for any E [n]:
P(a < &lggg) = o(n"
Proof. By Lemma 4.2 for any E [mi], the genie score 2 is given by
2/ Σ log (Atg))
Σ log
( ((Acg) log
P
log
S+ (v:) S_ (1:)
@(A:s)
P (A.g)
1- p)
JECT
JEC
For convenience, we define X; = 2/- log
1-p For any E C+ and any e, >
P(o 2 < < n) = P(2 < looog = IP (X, < (1 + (1)) logn) = PP (e( < {((loo(())) logn
le log (exx
25

---

Published as a conference paper at ICLR 2025
We now analyze
P+(Aij) 2(Ais)
Q(Ais)
(Bk)
E e
E
exp
-t
Σ
log
+ Σ log
P-(Ais)
+ log
8_ (yr+)
jECt
JEC=
((1ig)
P- (Aig) ((Ais)
S-(w:) (vi)
E
exp
log
P+ (A(z))
+ Σ log
+ log
S+ (3/:)
JECT
JEC
= E
flog
((44)) P41
II jEC
A log P-tdy) (4(7
e lon
8-19d) 34(05))
jECT
((An))
(P-(An)
)
S- (we) S+ (3t)
II E jECT'
II JEC
E
(A()))
Q(Ass)
((ttt)))---((mn((()))))))) -000--00000((00P)).0000000p000 (P
(S (1S)))
(using Lemma B.I and using community sizes conditioned on E)
e
(since (t - 1) = - (BB1-(())AA)
=e -L
Substituting this in our Chemoof-style bound, we obtain for any i E C++
P( < =llog n) S e (((()O(())))CH) ((+.)) log
When 1* > we have there exists E (0, such that L(1-t*) lim log CHI (+, -) > 1. Thus, there exists a constant e 0, and t" E (0, 1) such that for sufficient large n:
P log n) s e ((1+t) log n-f" log
Therefore, one can choose 81 81 (t", 0 small enough such that
2( < 8 log n) v e (11==1/2)log = 11).
We carry out exactly similar calculation for the community C_. For any E C_ and 1,5 >
P(a 2 < log n) = P( > -e - log n) = TP (X, > -(1 + o(1)) log = (eex: > ((1++(1)) logn
e log E [e
Simplifying
(+(A)))
2(Ais) P_ p_()))
S+ (w:) S_ (31)
E (x)) =
E
exp
Σ log
Q(Ais)
+ Σ log
+ log
JECT
JEC
(+)))))
((Acs)
S- (wi)
II E
II JEC=
E
((A:s)
P- (Aig)
S (ve)
jECI
= =((to(())(-)))(oaba) (1))) )+ (S, (())
(using Lemma B.I and using community sizes conditioned on E)
= =IHa(()))CC((++))
Overall, we obtain for any i E C+
P(o < <elogn) (((+)()))(CC(((+
26

---

Published as a conference paper at ICLR 2025
If > 1, then there exists t" (0, 1) such that L(t*) -00 log CH,(+, -) there exists constant > 0, and t* (0, 1) such that for sufficient large
1 and thus,
P log n) ( log n-f" log
Therefore, choosing : 62(t", > 0 small enough such that
2 < 82 logn) e (0-=002)) log o(n" 11)
Finally, choosing 8 min 82} > obtain for i [n]]
P(o 2 < 8 logn) = o(n )
concluding the proof of the lemma.
E ENTRYWISE BEHAVIOR OF EIGENVECTORS.
Abbe, Fan, Wang, and Zhong Abbe et al. 2020) showed the powerful entrywise behavior of eigen- vectors for a general ensemble of random matrices under certain assumptions. Their result (Abbe et al., 2020), Theorem 2.1) applies more generally to eigenspaces; below we note special case of their result when the eigenspace has single eigenvalue.
Suppose A E R=xn is symmetric random matrix and A = E[A]. Let the eigenvalues of A be [Ai] 2 ... 2 Aml and their associated eigenvectors be [m)}) (defined up to rotation eigenvalues are repeated). Analogously for A", the eigenvalues and eigenvectors are |사il [A,]]] and {u, hE(m) respectively. For any fixed (A,, U;), define the eigengap quantity
A = |77 A min | - X71-
(17)
je[m|((F)
Here we define the eigengap for the special case of (Abbe et al. 2020 Theorem 2.1) applied to single cigenvector, rather than for an eigenspace associated with consecutive eigenvalues. For more general definition when the eigenspace contains multiple eigenvalues, see (Abbe et al. 22020] Equation (2.1)) We define == //,/ which always bounded from below by For parameter y 2 O, consider the following four assumptions.
A1 (Incoherence). || A²"
A2 (Row- and column-wise independence). For any m E [m]]. the entries in the m row and column of A are independent from others, i.e. {Aij : = or j = m] 1 {Aij i + m, + m).
A3 (Spectral norm concentration). For some do E (0, 1), suppose PP[[ A ~ 2 80-
A (Row concentration). Suppose :p(x:) is continuous and non-decreasing in R4 and sp(x)// is non-increasing for & > O. Additionally (p()) 0 and 32x (9xx(7;9(7)) < 1. Let there be some 81 (0, 1) such that for any m [n]] and w E F.
81
P ((4 - A w| S A
| Lemma E.1 (Theorem 2.1 Abbe et al. (0020)) Under Assumptions
10 with probability at least
1 5n 25,, we have
Au X
111
min
su4
+ +(())
A
E. ENTRYWISE ANALYSIS FOR EIGENVECTORS FOR ROS.
In this subsection, we will show that the top eigenvector of A sampled from ROS exhibits the entrywise behavior discussed above. More formally, we show the following lemma.
Lemma E.2. Fix p E (0, 1) and à R. such that max{|al [a], [b|} > O. Let (A, ROS,, b). Condition on 0² satisfying E from 13) Let A = E[A 0¹). Define (A1 un and (Xi, ut) as above. Then with probahility 1 (11)
Auj
min (=1)
sui
-
Xi
Vogg
for some constant C = 0.
27

---

Published as a conference paper at ICLR 2025
According to the definition the ROS model, we have A = zd
log (VLr vtu"
W
The entire
analysis is done conditioned o², the only randomness in this analysis is from the added noise matrix W. We verify Assumptions required to apply Lemma E.1 uusing similar ideas as (Abbe) et al. 2020 Theorem 3.1).
Let (Ai, ui) be the top eigenpair. The corresponding eigengap quantity defined in T7 is A = [A]] A minggien Dij - A. We begin by characterizing "i, Xj, and A'
First, observe that A' zd ( lugn/n)
Lemma E.3. Let ui) be the top eigenpair of A". Then
i (1+ (1)))
logn n
1100122 =1=
1
[1] = O Iggnon
T2
Proof. Note that u*u* v /ogn/n a rank-1 matrix. Let Ari
2 |^m be its eigenvalues. Then
we have that only non-zero eigenvalue is X1 / loo || 2 O(vn n) and the corresponding An = O. After zeroing out the diagonal, the entries of the corresponding eigenvector u*/ |1e01l will be perturbed by a factor of (1+0(1)) since
normalized eigenvector is u"/ |e=|12 and A2 =
the diagonal correction is of the order of O(v log m/a). Hence, we obtain of = (1 + o(1))))'' ||0"|l By Weyl's inequality, calculate the effect of zeroing out the diagonal the eigenvalue:
IIi - Ail S 1o T
/log zd (0'0-T (logn//) |1,
=0
log
Therefore,
log nt
log n || 1121 Oly log n// (1 + +o(1))
\o = λΙ + (111///))
1 x Vnlon.
Applying Weyl's inequality, for 2 S I n, we get | = Olvioz//n). Hence, A /n logn.
Proof of Lemma E.2 We will let y = 3/ Assumption For any E C+
A. 1/0(Vlogm) due to Lemma E.3 Let us now verify
| V CT a logn + |C_| 22122 logn
V (1 + p(1)) at logn n + (1 + o(1))( p)n. 2b log ([VVoon).
where the second step follows from using Lemma B.3
Similarly, also for any i E C_
log |4 V VI++ abb2
log @(vlogn).
n
n
Overall, combining these two we obtain || = O(vog S 3// A verifying As- sumption [ Assumption 2 on row and column- wiie independence trivially holds due to the i..dd noise matrix W (up to symmetry).
To verify Assumption 3 on spectral norm concentration, first observe that A 4 W, where W is the zero diagonal symmetrie matrix with i.i.d. (0, 1) entries. Applying (Bandeira et al. 2017 Proposition 3.3), we have that with probability at least 1 e
n/2 -n/2
A - A = ||] < ~
Therefore, Assumption holds with do e nn/2 We now turn our attention to Assumption 4 Let us choose (p(x) = cD for some constant > 0 which we will decide later. Clearly, is continuous, is also non-increasing in (0, Letting
non-decreasing in R, with (0))) 0, and (x=)//x k = 1, it is straightforward to see that 32x max ((+)} = 32ymax max(1, [1,c] c} = o(1) < 1, as 7 o(1.
28

---

Published as a conference paper at ICLR 2025
We now verify the concentration part of the assumption. Using Lemma
have A x
[if] 2 max{pe: (1 p) n. Therefore, it holds that for any e > 0, there is sufficiently large such that A 2 (1 max{pa", (1 p}b² ) h Moreover, for any fixed w E IR"
one can say that
Iewlla
(1 - c) max pa², (1 p)b²) Jn |wlllo c ||w|l2
||l1200 +0
V
2
vn 1/11111 lo p)b² b))
(1 - e)emax (pa?; p)b
")/">>)""(//g) Vlog ||l|
Additionally, for any fixed m E [n], (A - A") w ~N(0,, [|umm||mml]] l12) Therefore,
||w|||2
P
(A A" m w
A || 4
vn 1
2 P (I(A- - A") )m w| S (1 m)x (1 (1-p)b²) Jv log n [|lll2]
= P (IV(0, || 11211 $ (1 c)c pa"; ; (1 p)b²) /log n (|w|12)
2 P (Wi1,, (1-113)1 < (1 - -)) (pa" p))b²} /log n ||0l12
= P (I 1)1 & (1 m-x)mmaxpppt
p)) p/bppp//boo00 Vlog
2e -1--e) max mxxc))2nxx((pp (1 logm//
2
(using Lemma B.2
e)e (1
nv
2n 2 (1-c)² ?) max (pa (1x))
(1 e)e
62 log
Therefore, letting
2n 11---1- max (1--)))))
2 max{pa² 2, p)]p
61 (1 max (1 - p)bb ( logn'
and setting
get 61 o(1). Finally, applying Lemma E.1 obtain that with probability 1 - 80 201
- -11
Auj x
5n(n +(1)) + ||ill, + 711AA11220
min
11
* (=:1]
A < (1++c((++c))) h willo + y 1|AA"112
(since K = 1 and ((x) = cr)
A-
0 log
We used y= S(vlogn)' || 1I
0 (a), || 2-+00 Vlogn, n, and A vog n.
L
E.2 ENTRYWISE ANALYSIS OF EIGENVECTORS FOR SBM.
In this subsection, we show that the similar behavior also holds for eigenvectors sampled from the SBM. More specifically, we restrict ourselves to the case when the expectation A" (after the appropriate diagonal correction) has rank This is achieved when
b
+
b
02
In this case, the eigenvectors that correspond to the top two leading eigenvalues (in magnitude) exhibit the entrywise behavior, which is formalized in the following lemma.
Lemma E.4. Let p E (0,1) and a1, 02, b > such that 0102 # b² Let (A, ~ SBM, a1, 0z, b). Condition of such that the event E from (33) holds and let A == E[A o*). O(n-3)
Define ((As, )iE())) and {(x), ut) (i)ei as above. Then with probability
Aug
C
Aug
min (1E(t1)
8ru1
Vologlog logn
and min (26(1
82U2
X
vn log logn'
00
00
for some constant C = C(p,ai, b).
29

---

Published as a conference paper at ICLR 2025
This again requires verifying Assumptions for the top two eigenpairs. We note that Dhara al. 2022b) showed a similar lemma for the special case of Planted Dense Subgraph (PDS), and our proof just generalizes their results. In order to do this, we first note down couple of important lemmas. The first one directly establishes the spectral norm concentration (Assumption
3
Lemma E.5, Let p E (0,1) and a1 02 b > O. Sample o*) ~ SBM,, a1, a2 b). Condition on o² such that the event E from (3) holds. Let A = E[A o¹}. then there exists constant
c1 = C1 (p, a1, 02, b) > 0 such that
P(IIA- A'l2 S c1 logn) 2 n
Proof. The lemma is special case of (Hajek et 2016, Theorem 5), invoking the theorem with c c= 3.
The next lemma establishes that the leading two eigenvalues of A", in the rank-2 case, are different in the following sense.
Lemma E.6. Consider p E (0,1) and 01 02 > such that 01 F G. Let (A,o*) ~ SBM,, (p. 01, (22 b). Condition
labelling a' such that the event E from (33) holds. Let A == E[A o.}. Then the top two eigenvalues magnitude are given by Xi (1 (1))) log n and X = (1 + (l))) log n, for some non-zero constants 01 * 02 in terms of (p. a1 (p.01, consequence, [V] X51 = O(logn) n).
02, b). As
Proof. The proof follows similar arguments as the proof of (Dhara et al. 2022b Lemma 3.2). We note that they prove the special case of the PDS when 02 b. but the same argument directly generalizes as long as 0102 + 62.
Proof of Lemma E.4 The entire analysis is done conditioned on o* such that E holds. We will verify Assumptions] for the leading two eigenpairs. First note that after adding a diagonal matrix D, whose entries are O log ), the matrix A" D has rank 2, and its remaining eigenvalues satisfy
n
d ... An = 0, where |A1 2 ... | Applying Weyl's inequality for 3 S i n.
| A4 = | S ||D|| O(1o))/x).
(18)
By the definition of the eigengap quantity in 17 for both the eigenvalues respectively
A Mi min | #
A (log n) and A |
A min
Xi (logn),
where we used (18) and Lemma E.6 an inportant observation, that to venty Assumptions 44 for both eigenpairs separately, suffices to just verify them with A and such that
We also define Ki
a a
and R2
D+l A
We first make
A = min Ai A3} = O(logn) and k max Kk2
To verify Assumption first let 7 = 2 max (anx((n,,0 az b). Fixing any E C+.
|| 112 = V |CT79 (a)
(1 logn
blogn n 2
+ |C_1
n
n
- -va+ o(1))o
of log"
+ (1+ (1+0(1)) p)
(12 log" 2
log n n
n
n
Similarly, even for i CC
|Ai VlcHl (blogn) (blo0))))m) + +|C-i
(2 log
T log n Vni
Combining both bounds, we obtain
T Flog n
||A 11
<
vn
30

---

Published as a conference paper at ICLR 2025
We now define the parameter y in terms of A* and the constant e₁ from Lemma E.5
C1 Vlvlog
C1 Vlgg (1).
7 A
(log
Then 7 - 61 Vlog S2( n)) which dominates r ///g Vn. This implies || S Sn
verifying Assumption Assumption 2 trivially holds due to the conditional independence of the entries of A, conditioned on o². By Lemma E.5 Assumption holdd with 60 n
PP[II A S 74") 1-
To verify Assumption let
(2r + 4) logn
(0())
for x > 0 and (o(0) 0. A (1 log(1/x))
It is straightforward to verify that satisfies the desired property stated in Assumption and pp())
O (f/lg log m). Also, x ((1) since both Aj Až log n, and by Lemma E.6 also [ [
log n. This implies 32x max (p()) o(1) verifying the first part of the assumption.
To verify the row concentration part, we simply apply (Abbe al.
2020 Lemma 7) with p
log 7/1 and a = 4/T. We obtain that for fixed vector w R" and m
m
(2r + 4) log
TP (A A ml
| 00
2n 2n
max 1o
/nl wl
[wll2
Substituting the definition of A and ((.),
A3) w| s A ||lll 10 P ((A ((IA
||w||22
)) 2 2n
/n
/
which verifies Assumption
with 51 = 2n Finally, applying Lemma E.1
with probability
1 60 28,
On
Auj 8
S sn( (())(((()))))))))))))))))))) + ((>)) |1 + 7 111 =0
min E(
xi
A
Vn log log
We used y= @j (07) 0
log log ) || 0 (z))))))))))))))))) 11A11111111 2 =0
1og vn
and A
(log n).
Similarly, with probability 1 - (nO we have
Aug
=V(yilggTog))
min Aa (=
$2
0
Vn log logn
The proof is complete by union bound.
F PROOFS AND ALGORITHMS FOR ROS.
In Appendix F.1
first derive the form of genie scores. In Appendices F2 we give our spectral
algorithm formally and prove Theorem I Finally, in Appendix F3 we provide degree-profiling algorithm under enormous BEC and BSC channel.
F.1 GENIE SCORES' FORMULA WHEN NO SIDE INFORMATION
We start by noting the form of genie scores when no side information is present.
Lemma F.1. Fix p (0, 1) and a, such that max{[a], [b]} > 0. Let (A, ~ ROS, a, b, Then for any E [n]]
log
log n Iog"(( (IC (a?b - a?b?))
27 (a (a- b)
Σ jEC
Aij +b Σ Aij
+
2n
jEC
-log
P
1-p)
31

---

Published as a conference paper at ICLR 2025
Moreover, conditioned on the event E from 13 the genie vector 2" R can be written
z² (a -bly logn Au" + (1 ( log log (1=1) 1n o(1),
where = (p(a² a²) + (1 pb -a²b²)) n/ and v² is given by (2)
Proof. For ease of notation, we denote f(n) = v /ogg//. First, note that ROS is special case of
GBM with P+ AV 1n) P- NV2 f())) 1) and Q (abf (n). 1). Applying Lemma
4.2 for this special case, we obtain the Genie score expressions; for any E [n],
(Ar ((m))
(Ag (m)))))
2
Σ
log
JEC
(A3)
(
+
Σ
log
+ log
1- p
jEC
(Aig - abl(n))²
(Aig - -a²
Σ
2
jEC
+ Σ
(Aij - b2 f(n))²
(Au abf(n))2)
+ log
p
2
1-
jECm
(a² ab) Σ
Ai + (ab b²)((n) Σ Aij
SEC_
SEC
(nn
(ICT (ICT'1(a (a?2 d')+ C= (b*t -(bb)) + log
+ 2
1- P
log n
(a b
a
A A.+ + Σ Aij
n
JECT
SEC
log n +
(ICT'l(a26" -aa at)+ - a²b²)) + log
(19)
2n
1 1-p)
Conditioned on E, simplifying term from 19
log n
(ICT' - at) (( a²b²))
2n
log (pn(a'6² - -a') + (1 p)n (6* -2²b)) o())
2n
(pla26² a + (1- -obb3) log logn/2 o()
7 + o(1).
Therefore, substituting this in 19). we obtain that for any i [n]:
2 = (a (
b)
logn n
Σ jECI
Aug + Σ Aus
+ log {p))
+ o(1).
(1-p)
jEC
logn n v + + log
(a b)
[-p) + oo))
Writing the same for all i E [n] in vector notation, we obtain
2" = (a b)v logn Av + (1 ( log (i-)) 1n + o(1).
32

---

Published as a conference paper at ICLR 2025
Roughly speaking, these genie scores in absolute value log scale for both ROS and SBM. This is when the exact recovery becomes statistically possible and explains the scaling choices for both models.
F.2 SPECTRAL ALGORITHM AND PROOF THEOREM
Below is our spectral algorithm which takes A (and optionally y when available) as input along with the parameters and returns an estimator spec- One of the (two) score vectors formed by the algorithm approximates the genie score 2*.
Algorithm Spectral recovery algorithm for ROS, without or with side information.
Input: An nxn observation matrix and parameters (p. a, b). Optionally, side information y E ) such that we can compute likelihoods of laws S+, and S_.
Output: An estimate of community assignments spcc.
1: Compute leading eigenpairs. Compute the top eigenpair A, denoted by (A1,41) where
|Aıl 2 |nn
2: Compute coefficients of linear combination.
6 = v ()- (1- and y == (p(a212 - ++)++++0 (1 (b (b0=-))((-->>p"" -²(b)) log
2
3: Compute spectral scores. For any E {+l}, prepare the spectral score vectors as follows.
No side information:
( = sci u1 + 71nn
Side information:
S+ 8
(+)) sc/U1 + 71, + log
(1)
4: Remove sign ambiguity. For each E {+1), let x(+) sgn(2
No side information: Return Ōsee = arg (xx( Pfo"" = à(() A).
BEC or BSC side information: Return Espsc arg max (a) Poo' = و(ا) A. v).
The values c and y are carefully designed to emulate the genie score. Since the eigenvectors only recovered up to a global direction flip, we need to keep both candidates the algorithm. One of them is approximating the genie score well. Finally, whichever one has the higher posterior probability is picked in step To show the proof of the score approximation guarantee, we need the following lemma, whose proof is included at the end of this subsection.
Lemma F.2. Fix (0, 1) and a, b RR such that max { [b]} > O. Let (A,a*) ROS, (p, a, b). Condition on o² satisfying E from (13) holds for it. Then there exists constant == c(p, a, b) such that with probability (nn-3) the following event holds
{ log n
E
| S cclogn
(20)
Below is our primary lemma which shows the spectral and genie score vector approximation in too norm.
Lemma F.3. Fix p E (0, 1) and a, such that max [la], 1 [b|} > 0. (A, ~ ROS,, (p. a, b) and condition o² such that E from (3) holds. Optionally, let y Sl(o" S-, for the channel laws (S+,S_), Let 2 and 2(5) be the genie score and the spectral score vectors respectively for the corresponding model. Then with probability - o(1),
- (+) = o(log n).
Proof. First of all, note that conditioned on E, we have \o = (1 + o(1)) (1 + o(1)) o(1))
o1+
log ||011|2 and 2j =
Additionally, ||v* V C 1 (1 + TTV pmu + -
33

---

Published as a conference paper at ICLR 2025
Using these, simplify
C1 Aui (1+ AL)
Vologn(a ()aa (1 p)62)88/2
Au
log n
(a
A)
A1 A1 1|00|12
log n/n 1100
(21)
where in the last step substitute ||
Now the high probability event in this lemma is such that (i) the behavior of eigenvectors as stated Lemma and (ii) the event E₁ from (20) hold. By Lemma E.2 and F.2 they both happen with probability -- o11. Additionally, let be the sign for which the conclusion of Lemma E.2 holds.
We now analyze the three models separately.
No side information: For every [n]]
(x(+)
2,1
(c)s(u)) ) + -
(recall Algorithm 2
ea (AuT) + - 2
+0
Aj
vn log (by Lemma
E.4 and the triangle inequality)
log (a () + 2
(1 + o(1))
+ Olv logn)
n
(using 21 and C1 Vog n)
log ni
log n
(1 + +()))
(a b)(A 34 +
(a A) O(1)
n
+ 00 +(VVlog
(putting 2 from Lemma FT
= log n I(Au")& O(Vlo( o(log n),
(recall Ej from (20
n
Side information: By Lemma 4.2 and Algorithm 2 (step 3). when side information is pro- vided, both the genie score vector 2" and the spectral score vector 2 are achieved by adding In $ (v) to their counterpart when no side information is provided. Therefore, the triangle inequality along with the analysis in the no side information case gives us that for every i [n)], we have |2{*) 2 = o(logn) n).
In either case, one can equivalently write conclusions for all í e [m] together in vector notation
min (E+1)
(0) ="
(logn).
We are finally set to prove our first main result in Theorem
Proof of Theorem 7 We note that step 4 of Algorithm 2 keeps two candidates (ō(s) E {+1}} and chooses the one which has maximum posterior probability. Therefore, to show that òspe achieves exact recovery above the IT threshold, it suffices to show that one of the two candidates achieves exact recovery, and ÔMAP also succeeds above the threshold, which ensures that algorithm selects the correct vector by maximizing the posterior probability. The MAP estimator achieves exact recovery whenever > already shown in Proposition 2.10 It remains to show that one of (ā(+) E (=1}) succeeds. To this end, recall Lemma F33 that with probability o-)(1),
min #E (E(+)
(5)
o(log n).
0c
Moreover, whenever I* 1, by Lemma D.I and union bound over e [no), there exists 6 >> 0 such that
min of > 8 8log = -(())
iE(n]
34

---

Published as a conference paper at ICLR 2025
Taking union bound over these two events, there exists 0 and s* {+1} such that
P min (E
(a*) oj
ç log
o(1)
Since أ( = sgn(2 (en((()))) in step 4
we obtain Ø(*") achieves exact recovery. As a consequence, even Spec achieves exact recovery above the IT threshold. other words,
lim IP (ōspec succeeds)
70000
We finally return to the proof of the lemma already mentioned.
Proof of Lemma F.2 For each
[ra], first define Y, log (Au"). We first note that Y; is n
a Gaussian random variable as it is the sum of most n independent Gaussian random variables. Therefore, have Y; ~ NN(,,, of) for certain μ4; and o?, which will calculate later. Applying Lemma B.2 for any Y; (after normalizing) yields
P
-
Ms Avlogn e 8--g
Rearrangement of the terms using the triangle inequality along with a union bound over all i [n]]
gives us
(i
[n] |Yl S |pd + 40, lerl/oogg)
21-n
Therefore it simply suffices to show that for every i E [n], the quantity |p /oloyyloog Ollog n). To this end, we first observe that (Av*), " the sum
independent Gaussian random variables
all with means whose absolute values are O
log
Thus,
log [[(AA*)]
log n (n 1)
(v log
Ollg n).
n
T1
n
Similarly, (Av*), is the sum of n independent Gaussian random variables with variances O(1).
This gives
log (Au"); n
log n Var [(Au)) )
log -(nn)
of
Var
O(log n),
n
which also implies
40 log n Ologgn)
F.3 DEGREE-PROFILNE ALGORITHM FOR BEC AND BSC CHANNELS
The following is simple achieves exact recovery if side information substantial to shift the thresholds of exact recovery.
algorithm that tries to mimic the genie naively and
Algorithm Degree-Profiling algorithm for ROS in the presence of BEC or BSC side information.
Input: An n n observation matrix and parameters (p, a, b). The BEC side information y with parameter or BSC side information y with parameter
Output: An estimate of community assignments d'
I: Let S+ = {i y: +1},
1-1,,S_ S_ == {i =11, and
(pla²6² - a²) +1 p) (11p)(6t-a'63)) n/2.
Compute E R such that, for every i [m]
2 a(a -bl /
logn Σ
/logn
Ag + b(a b)/
Σ JES_
Aij +7.
n
jESt
35

---

Published as a conference paper at ICLR 2025
2: Prepare the degree-prooee profile score vector dP follows. BEC side information: For any E [n].
Zi
if yi = 0:
up 2
+00,
if y/ +1;
if y/ 1:
BSC side information:
1-a
ddp
+In
3: Return dpp = (gn()
The following our formal theorem.
Theorem 3. Fix E (0,1) and a, E R such that max [a), [6]} > O. Ler (A,o*) (p, Let y ~ BEC(a", (e) BSC(O*, ,a),, where
log(1/e) 3 and lim n n-00
log( 1-a)
lim
7 100000
log n.
log
for some B > O. Then I* from 6 is well-defined and there is degree-profiling algorithm (Algo- rithm 3 that returns the estimator Tap which achieves exact recovery whenever >> 1.
The following lemma plays crucial role in the analysis our degree profiling algorithm which formalizes the notion of receiving most of the labels correct.
Lemma F.4. Let o² E {+1}" be sampled such that each entry is i..d with P(o +1) = p. Condition on o² such that the event E from (13) holds. For any B >> we let y ~ BEC t) or y BSC(o* a)) for and scales described in Theorem 3 Define S+ {i yi +1} and
S_ = {i: y -1}. Then with probability 1 - o(1)
max {1++ \5+1.1C_ \S-1 00 7
1log20
Proof. First, recall that conditioned on the even E about a², have |C+ = O(n) and |C_|
(n)). We now consider the two types side information.
BEC side information: Observe that
E[|C+ S+1]]= Σ
Ply = =)
$ 1-
iEC
Then Markov's inequality immediately implies that, with probability O(n (8/2), we have
|C+ \ S54 S 1-28/22 (*/log")))
Similarly, we also have B[ \ S-]] - S n--3. Thus, applying Markov's inequality again implies |C_ \ S_| O11/1og"0 a) with probability On A simple union bound over these two events implies, with probability On 8/2) = o(1)
max {|C+ 541, \ S-1) -
(10gg
n
log
10
BSC side information: Under BSC side information, E| \ S+ a aCC1| S n and E[[C'_ \ a CC_| 1-3 Therefore, using the Markov's inequality for both of these sets along with a union bound immediately implies that with probability 1 O(n 0n--8/2) 1 (1))
max {1C+ |,41, - = log
36

---

Published as a conference paper at ICLR 2025
To bound the effect of the error terms when make 240 approximation to 2", need another technical lemma whose proof we include at the end of this section.
Lemma E.. Consider p E (0, 1) and a,b E R such that max [|a,, [b]} ROS,, (p, a, b). Condition on o² such that the event holds. Fix any set T c C+ or C_
Let (A.0*)
such that [T] = OOn l0 n). Then for any i E [n], let us define Y, v log
Ejer
P(VE [n]
M 1) 2 2 0n
Using this lemma, we now show that the degree profiling vector 24 is good approximation to the genie score vector 2" in loc norm.
Lemma F6.. Fix p E (0, 1) and a, b such that max [[a], |b] > 0. Let (A. ROS,, (p,a. b) and condition on o² such that E. from (13) holds. For B 0, let y BEC(O" (c) or y BSC(o", o.) where and scales as described in Theorem 3 Let z" and σ respectively be the genie score vector and the degree-profiling score vector produced by Algorithm foor the corresponding model of side information. Then (irrespective of the parameter values), with probability 1 o(1)),
||2" 20p = =(().
Proof. We first start by observing, in the case of BEC side information - is just formed by overrid- ing the entries of = from step of Algorithm 3 with too or - -oo depending on the side information 1. Also, for BSC side information, ddp is precisely how the genie score vector =" in the respective model of side information relates to the genie score vector without side information which we denote by z'.
label being
log [_o y. By Lemmas 4.2 this
Therefore, to show the lemma, it suffices to show that, with probability - o(1),
|| 21100 O().
BEC side information:
|| =1loc
max
|2| zi|
iE [n]
log Σ
log n
Σ Ai + log (1- o(1)
max (E(x]
a(a b)
Aij + b(a - b)
n
15+
jEC- \
(substituting z' from Lemma
F.1 and from Algorithm
< max (E(x]
a(a b
log n
Σ JEC+AS+
Aij
+ b(a b) log n
Ag
+ +O(1,,
(22)
JEC_\8_
where the last step follows from the triangle inequality. By Lemma R4 both |C+ AS+ and
CC_ \ S_| are bounded by O(n/ log n) with probability are chosen only based on the side information and hence independent of A, conditioned on a². Using Lemma F.5 for these set C., S.S. and C_ \SS as T, and using a union bound, we obtain that with probability 1 - (1))
o(1). Moreover, these sets
max a(a b) <E(n
log TL
Σ
Aij = 0(1) and max xc[1]
b(a b)
log nt
Σ Aij
-(().
n jEC 1
n jEC Vs
Substituting these bounds in
22
with probability o(1)
|| -21la0 =01).
37

---

Published as a conference paper at ICLR 2025
BSC side information:
|| 211oc
max iE(n]
|// zil
log Σ As a(a aa(a-bb)) (bpp
log Σ Asj
max k
a(a b)
n
n
jEC+ 15+
JES+IC4
b(a biv logn
Asj b(a bla-bly b) log
Aúj log 1 1-p) p) (1=))
+ o(1)
jEC-18-
jES- \C-
(substituting x' from Lemma
F.I and from Algorithm
log n (a b)²
Au - (a b)2 -a-b) log n
Σ Aij + log P
max [e(n]
p-p)
+ +0(
JEC+ SS4
JEC-
(since S+ 1C= 1- and S_ \C_ = C+ S+)
< max (c(n]
log n b)²
Σ Agg + (a- 1)2 JEC
log n n
Σ
As + +011,
(23)
n
JEC 1
where in the last step, we used the triangle inequality. Again by similar arguments, first | is OO n) with probability 1 (1)(1).
using Lemma R44 both IC+ \S+1 and |C_ ---
Using Lemma H55 for these set C+ \ (S and C_ S.S_ further implies that, with probability 1 1-o(1)
log Σ Ay
log n2
max iE(m)
(a b)2
0(1)
and
(a b)2
Σ Ai =O(). jEC-
sE[n]
jEC-
Substituting these bounds in 23 with probability - o(1)
| 211,0 =O(1)
Finally, we prove Theorem
We have already verified Appendix[ithal I" well-defined for BEC and BSC channels where and scales described in the thcorem statements. When 3 >> 0, by Lemma F.6 that with probability - o(1),
Proof of Theorem 3
0(1).
Above the IT threshold by Lemma D.I and union bound over [n), there exists 8 such that
min of x 8 blog EE|p]
= 1 o().).
Taking union bound, there exists
0 such that
IP min of dp > slogn o(1).
LE(n
Observing cap = P)) obtain dp achieves exact recovery, i.e.
lim P (ōap succeeds) 1.
2=000
We return the deferred proof.
38

---

Published as a conference paper at ICLR 2025
Proof of Lemma F.3 First of all, observe that Y, is Gaussian random variable. Let say Y;
NH,, ),), for some l4 and o > 0. Applying Lemma B.2 for any Y (after renormalizing) yields
Y p4l 2 logo 0,
P
e 8 log
Rearrangement the terms using the triangle inequality along with a union bound over all i [x] gives
E [m] M 2 | + 40, 40.y/logn) S sn
Therefore it simply suffices to show that for every E [rz], we have |uil + 40.y/lgg S 1. Indeed, we will show that these terms are o(1). To this end, first consider the term 40 n for any E [n]] Recall that Y; is the sum of most [T] i.id. Gaussian random variables, all with variance 1, scaled by v logn/n. Therefore.
log S
log' ( 40, 40. log
(11
of
[T] IT|=
=
o(1),
log n
n
where we used [T] (1/hog"" n). We now show that |M4| = o(1 too for all E [n]. which requires some casework. First consider T C C+, then for any i E C+:
log
log
1 $
a
n
n
log
Similarly, for any E CL:
log n
log
p
Jabl
log n
Exactly following the same arguments, we also get the same bounds on even when C C_. Overall, established that
P(Vi [n] |Y] 1) O(n
G PROOFS AND ALGORITHMS FOR SBM.
We follow the same structure: in Appendix G.
derive the formula for genie scores when
side information is available. In Appendix G.2 we present our spectral algorithm with the optimality proof. Finally, in Appendix G.3
we do the degree profiling algorithm.
G.1 GENIE SCORES' FORMULA WHEN NO SIDE INFORMATION
We begin by showing that, with high probability, all the vertices have degrees logarithmic in n. Lemma G.I. Let p (0,1) and 01, a2, b >> O. Lei (A, SBM, ai, u2, Condition o² such that the event E from 24 holds then. For = max (1, an, 02, b) let
E
: Σ
Ag S clog n
(24)
jEIm]
then with P(E1) = -
Proof. Note that the entries of A (up to symmetry) are independent conditioned o² There- fore, for any i E [n], the 2th row has independent Bernoulii entries with means either P1, P2 or q. where (P1, P21 q) (a1 0g b) logno// n/n. Therefore, defining X Binom(n, 7 Flog n/n), where max(u1, a2, b). we have that X stochastically dominates Σjeín Aij. for any i E [m). Then ap-
plying the Chernoff bound for Binomial random variables (Mitzenmacher & Uptal 2017 Theorem 4.4, Equation 4.3) we get, for any i [n]
Σ Ay > 6mx logn
< P. (X 6max(1, logn) 2 Glog 2-llog
O(n 4)).
JENN
Taking union bound over all E [n] yields the desired claim.
39

---

Published as a conference paper at ICLR 2025
We next analyze the form of genie scores without side information.
Lemma G.2. Let p E (0, and a1, 02 >
0. Let (A, ~ SBM, (p. a1, az, b). Denote
(PI. P2.P2. q) == (a1, 022 b) log n/n. Then for any i E [n]] the genie score can be written
x log P1 - g) ((1 - pı)
Σ jECT
Agj log
9 P2)
Σ
Aij + log
P
P2(1 - 4)
1 1- p)
jEC=
(1-P)
1 1-q
+10
+ |C='log
1 P2
Moreover, conditioned on the event E. from 13 and Fr from (24)
||2" - Aw" 7n = 0(1,
where w" E TR is a vector with entriey (w+, w-) = (log(a1/b) log(b/a2)) on locations of C+
and C_ respectively and y (p(b a1) + (1 p) b)) logn.
Proof. First of all, note that the SBM is a special case of the GBM model with Pt = Bern(p)),
P_ = Bern(p2) and Q = Bern(q). Using Lemma 4.2 for this special case, for any E [n]
Au A (1- - )(2 (1-AA)) Pi
A (1 - 4) (2-Acs)
2/ = log
+ Σ
log
Σ JEC
log
P-
gAs - ()(1-A())
Aus (1 - p2) (2-
P22
IECT
log
(1(11 9)
Σ
Aij + log
[9(1-12)
Σ
Aij + log
P
((1 - P1)
P2(1 - ②)
1-p) p
JECI
JEC=
1 1-P1 1-q q
1 1-9
| log
+ +1--'|
(25)
P2
To show the second part of the lemma, we further simplify
1 1--1 9 )
1+ P1 P1-9. 9 log
1 + (01 - b) log
log
log
log
0
(26)
(1 (1-P1) pi)
(1 pi )
n
In the last inequality, we used
x 5 logg1 (1 +x) for x 1. Similarly,
x+I
1 -/2 = log
= log 1 (b (2) log n
) log
log
1 112
1
(27)
(1 9)
9)
Recall the definition of event E from using
13 and Ej from 24
Conditioned on E E E1, we simplify
25
26 and (27
log
Pi - 9)
Σ
Asj + log
((1 P2)
Σ jEC=
Aij
(11 - p1)
p2(1 - -g)
jECT
=log
log (T)
(1)
Σ
Aij log
b
Σ
Aij 0
log
Σ Aij jc(m)
012
jECT
jEC
log
(1
Σ
Aij + log
b
Σ
Aij + o(1),
(28)
02
JECT
jEC=
where the last equality followed by conditioning on E,. We also simplify
1-P1 = |C log 1+ q - P1 ) = ICT log
+ (b a1 log m
| log
1 1-9
(1 (l-))
(1 - g)n
(b a1) log n
log² n
=
+0
q)n
n12
(using Taylor expansion of log(1 + x))
(b- a1) log + O (1 9)n
(log 2
(1+ + (n
n2
= p(b a1) log + o(1)
(29)
40

---

Published as a conference paper at ICLR 2025
Similarly,
log -
=-== log
1 P2 -9 9
= p)( log + o(1) (30)
P2
(1 p2)
Substituting 28
29
and
30
into
25
u1 2 log
Σ
Ai + log
b
Σ
Aij + p(b a1) () 8) log 0(1)
b
02
jEC
jec
Σ
Ai
+ w-
Σ
As + + (1) = A. + +
Jec,
SEC_
Writing the above for E [n] in vector notation, we obtain
|| (Aw* + 7l O(1).
G.2 SPECTRAL ALGORITHM AND PROOF OF THEOREM
In this section, present our spectral algorithm for the SBM that can emulate the genie. As discussed in Section 3 this requires taking appropriate linear combination of eigenvectors such that the top two eigenvectors such that e₁ u + Czuz approximates w" in the fo norm. The vector w is a block vector with entries (W+, w-) on the locations of C+. and C_. Recall by Lemma G.2 that
Q1 (T)
= log
and w = log
We first present subroutine that finds these coefficients (c1, c2). We will introduce the formal cor- rectness of the subroutine later, but first we provide informal discussion as to how these coefficients computed. Roughly speaking, both ut and uz also have block structure, and therefore, finding (ci, 22) just corresponds to solving a system of 2 linear equations. Also, the coefficients do not depend the locations of a" with +1 -1 labels, so exploiting this fact just do calculation as if C+ is on the first [on] vertices and compute the proxy for actual 4". This results into the following subroutine.
Algorithm 4 Find Linear Combination Coefficients
Input: The parameter set (p, d1 02 b) such that a1 * 6² (Rank-2) and the graph size Output: The desired linear combination (c1,02).
1: Let S S [n]] such that S = : S pn) and compute the matrix B E Rax= such that
a1 dogn/n Bi = blogn/n
if i, E S; if E S but j $ S if & S and j $ S.
logn/n
2: Compute the two eigenpairs (A1, 01) and (πg, 02) of B (note that B is rank-2).
3: Let w" E R=" be the block vector such that:
[= log(a, /b), w log(b/o2)
if E S; if gigs S.
w
4: Return (c1, 02) E IR2 that satisfies
11
C2
w
(31)
A1
Both ह and 02 are block-vectors and they are linearly independent. Thus, Finding (ci, 02)
corresponds solving system of 2 x 2 linear equations.
41

---

Published as a conference paper at ICLR 2025
We note that in the rank-2 case when 0142 F b², the vectors i1 and 82 have block structure and are linearly independent. Therefore, it is possible to span any vector with block structure, and in particular, even w". We now propose our spectral algorithm in the rank-2 case.
Algorithm 5 Spectral recovery algorithm for SBM (Rank-2)
Input: An nxn observation matrix and parameters (p, ai, 02 b) such that a 42 + b². Optionally, side information y such that we can compute the likelihood laws S+ and S_.
Output: An estimate of community assignments Öspec
1: Compute leading eigenpairs. Compute the top eigenpair of A, denoted by u1), where 2 |
An
2: Compute coefficients of linear combination. Run Algorithm 4 to find (c1, and
? = (p(b a1) (1 () b)) logn.
3: Compute spectral scores. For any ($1, 82) E (+1)², prepare the spectral score vectors
No side information:
2 = S1 + $202U22 + 71n-
Side information:
200) = 8101 + 8202 + y1n + log SSt
(v)
S_
4: Remove sign ambiguity. For each E {=1} let (+)) (1)
No side information: Return Espec = arg max (xt)) PP = و(5) A).
BEC or BSC side information: Return Sppc arg (ax PP = o(*) A, v).
Finally, when 02 12, from Lemma G.2 we have W4+ w log (4) In this case, we can just use the deterministic vector along I, to emulate the genie-score vector. Strictly speaking, in this degenerate case, we do not even need a spectral strategy to achieve optimality. Despite this, we just refer to this as spectral algorithm in the rest of the analysis for simplicity of exposition.
Algorithm 6 (Spectral) Recovery algorithm for SBM (Rank-1)
Input: An nxn observation matrix A and parameters (p, a1, 02 b) such that 01 b2. Optionally, side information y" such that we can compute the likelihood laws S+ and S..
Output:
An estimate of community assignments spoc-
1: Let
a1 ) : (p(b (16--a))- a1) a1)+ +11++1110 () - b)) log n.
c: log
2: Prepare the spectral score vector spec as follows.
No side information:
spec cAln + 711
Side information:
cAln 71, + +lo (
S. (1()))
spec
3: Return Gys:: =
We now show that the score vectors formed by these algorithms approximate the genie score vector in each case.
Lemma G.3. Consider p E (0, 1) and ai, a2, > Let (A,o") SBM, (p, ai, 0z b) and condition on o² such that F. from (33 holds. Optionally, let y Sl(o" S4, for the channel laws S_). Let 2t be the genie score vector for the corresponding model. Then with probability 1 (1)
Case a142 + for some = (81, E {+1]²
x- - (5)
o(logn).
42

---

Published as a conference paper at ICLR 2025
Case d1d2 b²:
|| - -2000 1l = o(log n)
Proof. Recall from Lemma 4.2 how the genie score changes in the presence of side information. In Algorithm [ (Step 3) and Algorithm (. this is precisely how the spectral score vectors are updated from the case when no side information is present. Therefore, it suffices to show that the score approximation holds in the case when no side information is present, which now will be the focus of the proof. The argument is exactly analogous to the one done used Lemma F.3 discuss the rank and rank 2 cases one by one.
We now
Rank-1 case: 01 = b². In this case, when no side information is present
|| 100 1100 || log( 71 0(1),
where the last equation follows from Lemma G.2 and
b and using that +/2 02 Rank-2 case: a 02 * B2 Fix (#1, s2) E { to be the signs for which the high probability event in Lemma E.4 holds. Define
be the vector from Lemma G.2 with entries (w+, w-
(log(a1/ /b), log (b/ (2) on the locations of C+ and C-_ respectively. In this case, using Lemma E.4
will show that with probability - o(1), we have
|| - 8101 $20282 = o(log n))
(32)
Combing this
32 along with Lemma G.2 implies the desired result: with probability 1 o()),
|
26)
< =- Aw" 7 l
Aww + +1,, 2(6)
= ||2" - Aw" 1nl ||A 8ICIU1 820282/loo (Step of of Algorithm 5)
= o(log n.).
It remains to show (2). Note that, we calculate (2),02) ) in Algorithm 4 using the matrix B where community sizes are exactly pn. But, condition on E, we have community sizes (1 + o(1)) and (1 + o(1))( p)n. Also, in A", we have zero diagonal, where as, the matrix B has diagonal entries of the order of (logn// n/n). These changes only affect the eigenvalues by the multiplicative factor of (1 o(1)) by Weyl's inequality. Therefore,
M (1 o()) and X3 = o01))
Moreover, the entries of uj in the locations of C+ are (1 + o(1) factor of the entries of in in the locations in S. By the same argument, one can say the same for ui in locations of C__ and on in locations of [m] \ S. and also for us and U2. From the way we calculate (c1, 02) in 31). we have
11
02
C1
+ C2
= w
Then the above discussion implies
C2ug,
(crui, >i
=
(1+o(1))
for i E C+ and w- (1+o(1))
+
for i E C_.
x
X5
25
Finally using Lemma
E.4
with probability 1 1-
Auj A9
Aug
A|w"
010102 S202U2llo < Aw" -1
C2
+0(1)
100
Aui
Aug
Aut
AuA
(1 o(1))
c1
+
C2
6j
C2
+0(1)
X;
X
X;
=(1) (max(14:ll1) C1 uj
(1
22
v
(iem)
X
o(logn),
where the last Step follows by using Lemma G.I and (ci, 02) chosen in such way that the e X; and ezu5 are O(1) by 31.
entries of vectors
We finally combine all the pieces and give the proof of Theorem 2
43

---

Published as a conference paper at ICLR 2025
Proof of Theorem
We break into cases.
Rank 1, i.e. a1 42 = b2: First note that Algorithm 6 creates a score vector 2 IR" such that ||= _
olog n) by Lemma G.3 Using Lemma D.I whenever /* >, there
exists ç > such that
2f <<logn) n) o(n
Taking union bound,
P(Vi [n], o7 10 > <loo n) = o(1) Finally, the algorithm outputs spec sgn( (gn())pec) (Step 3). this immediately implies
P(ōspec = 11
2. Rank 2, i.e. 0102 * 12:: We first note that whenever 5 >> 1, the estimator M achieves exact recovery by Proposition 2.10 That is with high probability, we have Ō a², unless a1 d2 and no side information, in which case MMA E {#o*). Recall that Algorithm 5 creates four candidates for o² and chooses the one with maximum pos- terior probability. Due to statistical achievability, it suffices to show that of the {o(()) (2), {=1]²} maintained by the algorithm is of with high probabil-
ity. To this end, recall Lemma G.3 that with probability 1 - o(1)
2 2 2 = o(log n².
min {+1)
Combining this with Lemma
D.1 there exists 8* E {+1)2 and ç > 0 such that
P min o1 (0*) > llg = - o(1).
FE|m]
obtain g(=") o² with high probability. Overall, we established that ôpecc achieves exact recovery above the IT threshold.
after taking union bound. As g(*)) sgn(2(*")) in Step 4
G.3 DEGREE-PROFILDE ALGORITHM FOR BEC AND BSC CHANNELS
Algorithm 7 Degree-Profiline Profiling algorithm for SBM in the presence of BEC BSC side information.
Input: An observation matrix A and parameters (p, a1, a2, b). The BEC side information with parameter or BSC side information with parameter a.
Output: An estimate of community assignments åpp
1: Let S+ := {i y +1), S_ == {i: : y: -1), and : (p(b-ar)+ p) b)) logn. Compute e _ such that, for every i [n]
= log (
Σ JES+
Aug + log
b
Σ
Aij +7.
02
JES_
2: Prepare the degree-profile score vector 4 as follows.
BEC side information: For any E [n].
2
if yi 0;
2,
+00,
3/1 = +1:
if = 1:
BSC side information:
1 -
.pp
loog
3: Return ōap = 4))
44

---

Published as a conference paper at ICLR 2025
The success of the Degree-profiling algorithm is formalized in the following lemma.
Theorem 4. Let p E 1) and a1, 01,02,b b > y ~ BEC ,c) ory ~ BSC(O", a)), where
0. Let (A,o*) (p, ai, a2, Let
lim log(1/c) and lim 1-00
log( 1-a)
logn
log
for some B >> O. Then I' from 6 is well-defined and there is degree-profiling algorithm (Algo- rithm ( that returns the estimator Gap which achieves exact recovery whenever
Again to prove that our approximation is good enough when using S+ and S_ as proxies for the actual communities, we will need technical lemma bound the error terms, whose proof include the at the end of this section.
Lemma G.A. Consider E (0. 1) and a1, 02, > O. Let o²) ~ SBM,, (p. 01, 02. b). Condition on o² such that the event E from (13) holds. Fix any set T C C+ or T C- such that [T] O(n/ log" 10 n). Then for any E [m], define Yi := Ejer Aij- Then
log 2 1 Ol-O
P
Vi [n] :Ys.
log logn
Using this, actual genie scores.
show that the degree-profiling scores are indeed good approximations of the
Lemma G.5. Fix p E (0.1) and u1, 02. b > Let (A, ~ SBM, a1 02
(2,b) b) and condition on o* such that E from (13) holds. For 8 0. let y BEC(O*, y BSC(o* ,a) where e and a scales as described in Theorem 4
Let x" and dd respectively be the genie score vector and the degree-profiling score vector produced by Algorithm 7 for the corresponding model of side information. Then with probability o(1).
log
2Pp 11
log log
Proof. The proof has similar calculations as in Lemma F.6 for ROS. We again first start by noting that d is just formed by overriding the entries of from Step I of Algorithm 7 with +oo depending on the side information label being +1 or -1 under BEC channel. ATso, in Step under the BSC channel, have 2d change under both types of side information. It suffices to show that, with probability 1 - o(1)
log (- y. Recall Lemma 4.2 as to how the genie scores a
|| =l =0 log
log log n
where the genie score vector without side information and is formed in Step Recall that Eg holds with probability On from (24). Using Lemma G.2 along with the triangle inequality we obtain the following.
BEC side information:
|| - 2 2l1oe
max TEIn]
12/ zil
max log EE
a1
Σ JEC_ AS+
Au + log (
Σ Aij + +1(
JEC_ 18_
where substitute 2' from Step From Lemma F.4 both IC4 SS41 and |C_ S_ are bounded by O(n/ log" 10 n)) with probability o( 1). These sets independent of A and are chosen based on y. Using Lemma G.4 for these sets, with probability o(1)
|| - 2/100 < max log
a1
Σ
At + log
Σ Ag +0(1) =0 log n 1EC_
2E(n]
a2
log log
JEC- {s_
45

---

Published as a conference paper at ICLR 2025
BSC side information: There additional error terms caused by the sets S+ S_ C_:
C+
and
|| 2|1,0
max iE(N)
12/
zzl
log
a1 b
Σ
Aij
log
a1
Σ
As
iE(m)
b
18+
IC_
+ log
b
Σ
Aij log Σ
Ag
+0(1)
(12 JEC \ (substituting z' from Lemma G.2 and from Step 1
JES \C
0(1) max *E|n]
Σ AG+ Σ Ag
+ +11)
iS
JEC 18
(since S+
|C C_
\S_ and S_ \C_ C+ S+)
Exactly the same argument of using Lemma (nn/ log. bility o1)
F.4
both C
S+1 and |C_ S_ is
10 n) with probability o(1). Using Lemma
G.4 for these sets, with proba-
|| =l1oc = =0
log
log log n
We finally prove Theorem
Proof of Theorem We already discussed in Appendix C that I is well-defined. When 0, by Lemma G.5 with probability - o(1),
dp O(1).
Above the IT threshold by Lemma D.I and union bound over [n]. there exists 8 such that
P
min of 2 llgg 1 o(1).
iE|n]
Taking a union bound of these two events, there exists > such that
IP
min of dp > s log 1 - o(1).
Observing dap = 4P) in Step of Algorithm 7 we obtain opp achieves exact recovery, i.e.
lim P (ōup succeeds)
2-+00 30
We finally return to the skipped proof of a technical lemma.
Proof of Lemma G.4 Fix any set T according to the lemma and define (Y, E [n]]. Let T max a1 ag. b} and Y Binom([TT) zlogm). Observe that for any i [n]. we have Y; is stochastically dominated by Y. Applying the following Cherooff bound for Binomial random variable (Mitzenmacher & Upfal, 2017] Thereom 4.4): for any > 1 and X Binom(N,p) p).
P(X 2 rmp) & (e/r) we obtain for any E [m]
log
log n log log n
e/7 logn/n log n/ log logn
Tox
P Yi
S P ( <
<
log log
log log Jog.
log log
100+0(1)
log 10
A simple union bound over all i E [r|] gives us
log
P
Vi E [n] Y
2 1 - 21-0(n-3)
log log n
46


Reviews:
[{"review_id": "6947vxFQZC", "reviewer": "Reviewer_Appg", "summary": "This paper considers the problem of recovery of two-community block\nmodels. It sits in the context of a broad literature on detectability\nlimits, exact algorithms, etc. The particular setting considered by\nthe authors is one of a general sort of block-model random matrix\nbased on a given partition/distribution model, along with a vector of\n\"side-information\" that is aligned with the block structure in some\nway. The authors study the information theoretic limit of this\ndetection problem via simple spectral methods, and by studying\n\"genie-aided estimators.\"", "questions": "My only concern with this paper has to do with the formatting issue raised in the weaknesses section. If this is a typical approach that is commonplace and accepted in ML conferences, then I am willing to cede that point.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "This is a well-written paper -- there are quite a few moving parts\ninvolved in this work, but the explanation was clear and easy to\nfollow. The authors ought to be commended for clear technical\ncommunication. I do have onemajor misgiving about this, but that \nis saved for the weaknesses section.\n\nI am admittedly not too familiar with the literature on exact recovery\nof SBMs beyond the paper of Abbe (2018), but the results here seem\nquite good, and fit into the surveyed prior results nicely. I\nappreciate how the recovery guarantees are accompanied by specific\nalgorithms, rather than proving detectability in merely an abstract\nway.", "weaknesses": "My critique of this paper is not one aimed at the strength of the\nresults -- indeed, I found the results to be nice, and the exposition\nto be quite good. However, I have the sense that the main body of the\npaper was merely a rough overview of the \"real paper\" hidden in the\nappendix. I understand that for space reasons, lots of ML papers have\nto put substantial content in the supplementary material. I don't have\na deep argument for why this is the case, but I get the feeling that\nthis work is better-suited for a journal format. For instance, one of\nthe main constructed algorithms that attains exact recovery\n(Algorithm 2) is only given in the supplementary material. It would be\nmore appropriate to structure the paper so that the algorithm is given\nand explained in the body of the paper, with other variants possibly left\nto the supplement.\n\nI should note that although I am a reader of theory papers of this\nsort, I have not reviewed many of them in the context of ML\nconferences, so I am ultimately willing to defer to the other\nreviewers on this point.\n\nOther notes:\n\n(I am not holding the following against you in any way -- deadlines\ncan be tough!)\n\nPlease check the paper for spleling mistakes -- I spotted a few such\nas \"Gaussain Features\" and \"shifing the eigenvector combination.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GAFp9SCTcy", "reviewer": "Reviewer_T3f8", "summary": "This paper addresses the problem of exact community recovery for general two-community block models with node-attributed side information. The authors consider both Gaussian and Bernoulli matrix models for the edge observations, as well as a general side information channel, including Gaussian Features and Binary Erasure Channel. Based on the recent work of Dreveton et al. (2024) on the information-theoretic limit on this problem, the authors demonstrate the algorithmic achievability using a spectral algorithm that incorporates side information with the eigenvectors of the observed edge matrix. The main technical novelty lies in establishing a rigorous connection between the spectral estimator and the genie-aided estimator by the results on the first-order approximation of the eigenvectors in Abbe et al. (2020).", "questions": "1. On Page 6, $L(t)$ and $I^*$ are introduced to characterize the information theoretic limit. Are there any general sufficient conditions that ensure $L(t)$, and consequently $I^*$, are well-defined? \n\n2. In Section 5.1, degree-profiling algorithm is mentioned as having certain caveat. However, it is unclear to me what this algorithm refers to. Perhaps adding a brief summary of the key points of this algorithm would improve clarity.\n\n3. On page 9, it is stated that an approximate linear combination coefficients $c_i$ such that $w\\approx \\sum_{i=1}^K c_i/\\lambda_i^* u_i^*$. Is there any intuitive explanation for why $w$ is approximately in the span of $u_i^*$? Is this result purely from the computations of the specific model (Gaussian and Bernoulli), or is there a broader rationale suggesting that this holds across more robust models? \n\n4. Regarding the algorithm, do the parameters $c_i$ and $\\gamma$ need be explicitly computed from the model parameters, or is there a possibility to estimate them using only the adjacency matrix $A$ and the side information?\n\n5. This final question may not be directly related to the problem considered in the paper. Dreveton et al (2024) provides  the information theoretic limit of exact recovery in terms of $I^*$.  I am curious whether the regime $I^*<1$ can be further split. Specifically, could we identify a sub-regime where exact recovery is achievable even without the side information, and another sub-regime where side information is essential with some specific conditions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-structured, with clearly stated objectives and supported arguments. It provides background definitions and results on related models, which greatly aids in understanding the topic. The novel approach of connecting the eigenvectors to the genie-aided estimator is particularly intriguing, contributing to the design of an efficient spectral algorithm. Additionally, the rigorous mathematical derivations are well-organized in the appendix, offering solid theoretical support.", "weaknesses": "Due to the page limit, I feel that some important details have been deferred to the appendix. For instance, I would like to see a more rigorous discussion in the main context on the special form of the genie score vector, $z^* \\approx Aw + \\gamma I_n$; how $w$ can be derived from the model, any regularity conditions needed for this approximation, and whether this form extends to models beyond Gaussian and Bernoulli. I suggest moving part of the theoretical discussion into the main text and possibly relocating some of the preliminaries to the appendix.\n\n Additionally, I am uncertain about the robustness of this algorithm, as the coefficients $c_i$ relating $w$ to eigenvectors must be computed from model parameters. However, in practice, we typically observe only the adjacency matrix and side information, without access to underlying parameters like $a_1, a_2, b$ in ${\\rm SBM}_n(\\rho, a_1,a_2, b)$. A discussion or clarification on this would be beneficial.\n \n  Another limitation of this paper is the lack of a numerical study. I suggest including simulation examples that compare the proposed algorithm’s performance (in terms of accuracy and computation cost) with the existing two-stage algorithms. This would strengthen the paper by demonstrating the practical advantages of this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YmiTYyqZfZ", "reviewer": "Reviewer_dGJq", "summary": "The paper studies block models with two communities, where each community has a general form of edge distribution. Side information on nodes is also considered. The authors specifically focuses on the case of Bernoulli and Gaussian distributions. The paper then proposes a variant of spectral algorithm to recover the community structure in the model, and provides statistical bounds for exact recovery of the signal.", "questions": "- I understand this is a theoretical work, but have the authors verified their algorithm on any dataset? \n- What is the computational complexity in terms of n?\n- Is it possible to generalize this work to the case of multiple communities? If not, what are the technical difficulties?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well organized and easy to follow. The notations and definitions are mostly self contained.\n- The authors provide the statistical bounds for exact recovery in the case of the Rank One Spike (ROS) model and the Stochastic Blockmodel (SBM).", "weaknesses": "My biggest concern is that some of the language in the paper seems overclaiming. For example, the authors state that the paper proposes a \"unified model\" and \"unified proof framework\". The amount of novelty and contribution is unclear to me. Can the authors specify, preferably in bullet points, their new results, algorithm, bounds, proof techniques, or experiments?\n\nBeyond that, I have some more detailed questions:\n- The paper aims to provide a unified framework of analysis for at-most-two-community block models, but the results in Theorem 1 and 2 only target two specific and arguably \"simpler\" classic models. Why is that? Is it possible to give a bound based on the definition of P+, P-, and Q, for instance? \n- Section 3.1: Does the information-theoretic bounds in Prop 3.1 contain anything novel, or just cited as is from [Dreveton et al., 2024]? If it is the latter, I strongly believe it should be moved to the preliminary section and not put in the \"Main Results\".\n- Theorem 1 and 2: The exact recovery condition depends on I* > 1. Is there any way to calculate this efficiently? From a reader's perspective, I'd love to see many examples of two community models and know how their parameters are related to this I*. For example, can the authors relate I* to p and q in the SBM?\n- The proofs like the concentration inequalities and the spectral analysis in the paper seem standard. In fact the union bound strategy feels similar to the ones in E. Abbe's and Dreveton's work. What are the technical contribution of this paper? Is there any proof technique that can be used in the future?\n\nMinor:\n- Bern() used but not defined on the first page.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iFqJ4HuSno", "reviewer": "Reviewer_Zdp2", "summary": "This paper addresses the problem of exact community recovery in two-community block models with node-attributed side information. The primary contribution is the design of an optimal spectral algorithm that achieves the information-theoretic limits in various settings. The general block model in this paper encompass  rank-one spike Gaussian model and SBM, and the side information incorporates GMM and two types of \"noisy'' labels.", "questions": "See weaknesses above. Also, the paper could benefit from a careful proofreading. For example:\n\n1. Gaussain -> Gaussian on page 3.\n2. In Algorithm 7,  $\\alpha_n$ is not defined. Should it be $\\alpha$?\n3. In Algorithm 6, the input section ends with two periods.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized, and the arguments flow logically.\n\n2. The claims are solid, and the proposed framework covers a broad range of interesting models.\n\n3. The results provide theoretical insights into community detection with side information and demonstrate the optimality of spectral methods.", "weaknesses": "1. Some related literature is missing, e.g., [1]. Specifically, the SBM model with $\\rho = 1/2$ and Gaussian Features aligns with Section 4 in [1] and should be cited and compared. Additionally, for the SBM with GF where $\\rho = 1/2$ and $a_1 = a_2 = a$, the expression for $I^*$ takes a simple form in Equation (4.4) of [1]. Providing explicit forms of $I^*$ for other models would enhance interpretability of the results.\n\n2. For SBM with BEC/BSC, the algorithms assume prior knowledge of parameters $(\\rho,\\varepsilon, \\alpha)$. The paper should mention this clearly and discuss why it's reasonable to assume this prior knowledge, or suggest how these parameters could be estimated. From a theory standpoint, achieving optimality might require paying a cost for adapting to these parameters, especially in regimes $\\varepsilon = n^{-\\beta}$ and $\\alpha = n^{-\\beta}$ for $\\beta>0$. \n\n3. The two-community assumption limits the algorithm’s practical use. While I understand that the optimality of the spectral algorithm depends on this assumption, the statement in Appendix A, \"The entire framework of genie-aided estimation naturally generalizes to the multi-community case,\" is confusing. Can the authors elaborate on how the spectral algorithm could be modified, for example, to handle $K=3$ communities?\n\n4. There are no experiments. It would be helpful to include numerical experiments demonstrating the algorithm’s performance on the specific models considered.\n\n[1] Abbe, E., Fan, J., & Wang, K. (2022). An $\\ell_p$ theory of PCA and spectral clustering. The Annals of Statistics, 50(4), 2359-2385.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)