acceptodds
Under review as a conference paper at ICLR 2027

Weak Sparse Relations Add Up: Sharp Limits for Joint Community Detection

Abstract

We study community detection in the binary symmetric joint stochastic block model (JSBM), which couples a sparse graph on items to a sparse item–feature relation with latent-labeled features. Cavity analysis predicted its detection boundary and Bayes-optimal BP behavior, leaving open a matching information-theoretic converse and polynomial-time achievability theorem. Let denote the mean graph and item-side incidence degrees, the corresponding one-edge label correlations, and . For fixed known parameters away from criticality, we prove the sharp threshold . For , the planted and null laws are mutually contiguous and weak recovery is impossible; for , they are asymptotically singular and randomized-polynomial-time weak recovery is possible. Thus two individually undetectable relations can jointly support efficient recovery, with no statistical–computational gap. The proof combines typed-cycle and self-avoiding-path expansions with a forest–parity reduction that controls overlaps sharing latent features, half-edges, or reversed segments. Large-scale BP experiments recover the predicted phase geometry and joint rescue, while weighted spectral inference also illustrates joint recovery.

Primary area:
learning theory
Keywords:
Community detection, joint stochastic block model, sharp detection thresholds, forest-parity method, typed self-avoiding paths

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_6grEOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the problem of community detection in the binary symmetric joint stochastic block model, where information about the label of an item (σi∈\sigma_i\in {±1\pm 1}) comes from a sparse item–item graph $A = (A_{ij}:i,j\in [n]) $ and a sparse item–feature graph F=(Fiμ:i∈[n],μ∈[m])F= (F_{i\mu}:i \in [n], \mu \in [m]) with latent item and feature labels {σi:i∈[n]\sigma_i:i\in [n]} and {τμ:μ∈[m]\tau_{\mu}:\mu\in [m]} respectively. For fixed known parameters involving average degrees dA,dF>0d_A, d_F>0, edge label correlations sA,sF∈(−1,1)s_A, s_F \in (-1,1), and m/n→γ∈(0,∞)m/n\to\gamma \in (0, \infty), the authors establish the sharp weak-recovery threshold at Λ=dAsA2+dF2sF4/γ=1\Lambda=d_As_A^2+d_F^2s_F^4/\gamma=1. They show that weak recovery is impossible for Λ≤1\Lambda\leq1 and achievable in randomized polynomial time for Λ>1\Lambda>1. Moreover, they prove mutual contiguity of the planted (PnP_n) and degree-matched null observation (QnQ_n) laws strictly below the threshold (Λ<1\Lambda <1) and asymptotic singularity strictly above it (Λ>1\Lambda >1).

In the subcritical case (Λ<1\Lambda <1), the proof of Pn◃QnP_n \triangleleft Q_n goes via proving uniform boundedness of the second moment of the likelihood-ratio �0��0� under the null QnQ_n. The proof of Qn◃PnQ_n\triangleleft P_n goes through analysing typed-cycle statistics and establishing distributional convergence of LnL_n under the null QnQ_n to a strictly positive random variable L∞L_{\infty} with mean one. A computation similar to Qn(Ln2)Q_n(L_n^2) obtained by fixing finitely many item labels establishes impossibility of weak recovery. In the critical case (Λ=1\Lambda =1), they establish information contraction on the two-type broadcast tree and transfer non-reconstruction to the graph.

In the supercritical case (Λ>1\Lambda >1), weighted centered typed-cycle statistics provide use a natural hypothesis test that establishes asymptotic singularity P⊥QP \perp Q. More precisely, it shows that ∥Pn−Qn∥TV→1\|P_n-Q_n\|_{TV} \to 1. Similarly, weighted self-avoiding-path estimators produce a randomized polynomial time estimator achieving weak recovery. The principal model-specific analysis in the recovery proof concerns overlaps between paths that share feature incidences, including partial wedges, while retaining the sharp threshold constant. Color coding and SDP-based Gaussian rounding complete the polynomial-time recovery construction.

The numerical experiments use belief propagation and weighted Bethe–Hessian inference to illustrate the predicted phase transition, recovery from individually subcritical relations, and finite-size and convergence effects. These experiments evaluate different algorithms from the recovery procedure analyzed in the proof.

Critical strengths

The strongest contribution is the rigorous threshold theorem for the sparse binary JSBM, including non-recovery at the critical point and polynomial-time achievability above it. A rigorous justification of a previously predicted threshold is useful.

The treatment of sparse incidence overlaps is the most potentially substantive technical component. In particular, the analysis retains partially shared feature wedges and tracks item and feature identifications while preserving the sharp threshold constant.

Critical weaknesses
  1. The mathematical and conceptual advance over the closest prior work is not sufficiently established.

The additive threshold and the possibility of combining individually insufficient relations were already predicted by the cavity/BP analysis for the JSBM by Zhou, Li, and Zhang (2020), as the paper acknowledges. The contribution therefore lies in rigorously establishing this prediction and developing the technical arguments required for the sparse relational model.

However, the proof architecture also has substantial precedent. Hopkins and Steurer (2017), Algorithm 3.3, already construct a matrix from centered self-avoiding-path products, apply a minimum-Frobenius-norm semidefinite projection, and perform Gaussian sign rounding. Their Section 2.5 supplies the color-coding approach. Moreover, the proof of their Lemma 3.7 already uses the even-degree symmetric difference of two paths and the absence of nonempty even subgraphs in their intersection to eliminate label-dependent terms. Thus the central parity cancellation. underlying the present paper’s Lemma 5 is an established ingredient. Lu and Sen (2023), Section 5, extends the path-estimation framework to graph-plus-covariate observations.

I recognize that sparse Bernoulli incidences require different moment and overlap calculations, including the treatment of repeated incidence scores with label-dependent conditional second moments, and I am not claiming that these references already establish the full theorem here. The remaining contribution appears to rest primarily on the sharp typed-overlap estimate, especially Lemma 2 and its supporting enumeration. The paper identifies this obstacle, but I would like a more explicit comparison explaining which existing estimates fail, what new argument replaces them, and why preserving the sharp threshold requires that argument.

A rigorous theorem for this model is valuable. Nevertheless, after reading the proofs, I am not persuaded that the additional conceptual and methodological advance is sufficient for acceptance.

  1. The exposition does not adequately develop the proof as a sequence of informative mathematical steps.

This is my more substantial concern. The paper contains a roadmap, numbered lemmas, worked examples, and high-level explanations in Sections 4–5. My concern is that these components do not make the conceptual dependencies and the distinction between inherited arguments and model-specific estimates sufficiently transparent. I would find the paper considerably more informative if the central intermediate results were stated together with a clear explanation of their purpose and their role in the overall argument. In my opinion, it would be have been much easier to follow, if the authors could "factor the paper into smaller pieces, for instance by making plenty of lemmas" (https://terrytao.wordpress.com/advice-on-writing-papers/).

For example, in the sub critical regime Λ<1\Lambda <1, the result that Ln→dL∞>0L_n \overset{d}{\to} L_{\infty} >0 under QnQ_n implying Qn◃PnQ_n \triangleleft P_n and the related one on uniform boundedness of the limit of Qn(Ln2)\mathbb{Q}_n(L_n^2) showing Pn◃QnP_n \triangleleft Q_n could have been carved out as separate lemmas individually, as these are individually neat and self contained results in themselves. Moreover, the the proof of the impossibility of weak recovery could have been well segregated as a lemma that requires going a little beyond computing Qn(Ln2)\mathbb{Q}_n(L_n^2). Isolating these statements would help readers distinguish standard probabilistic implications from the calculations specific to this model.

We empahsize that these arguments above build on established probabilistic techniques. In particular, likelihood-ratio second moments and small-subgraph conditioning were already applied to establish subcritical contiguity as well as impossibility of weak recovery in the sparse stochastic block model by Mossel, Neeman, and Sly (2015). The paper should therefore explain more precisely which model-specific estimates constitute its additional mathematical contribution.

Similarly, in the supercritical regime (Λ>1\Lambda>1), Appendix C.1 already presents the weighted centered-cycle test. Stating its consistency and asymptotic-singularity conclusion as a separate proposition would improve navigation. Cycle-count methods for proving supercritical asymptotic singularity already appear in Mossel, Neeman, and Sly (2015, Theorem 3), while efficient weak recovery above the sparse-SBM threshold was established by Mossel, Neeman, and Sly (2018). These provide natural reference points for explaining the additional arguments required by the present model.

Moreover, the recovery proof would be more informative if it introduced the abstract matrix-to-label criterion, currently stated in Lemma 12, earlier in the argument. It could then organize the construction around unbiased path estimation, the exact path-pair moment identity, the sharp typed-overlap bound, polynomial-time evaluation, and rounding. The paper already contains these ingredients; my concern is that their conceptual roles and dependencies are not sufficiently explicit. Each central step should explain which obstruction it resolves, why its quantitative strength is needed, and how it differs from the corresponding argument in prior work. In particular, I found that understanding the additional insight in the central overlap estimate required reconstructing much of its motivation from the combinatorial bookkeeping.

References:

  • Zhou, Li, and Zhang (2020), “Phase transitions and optimal algorithms for semisupervised classifications on graphs: From belief propagation to graph convolution network,” Physical Review Research 2, 033325.
  • Hopkins and Steurer (2017), “Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems.” See Algorithm 3.3, Lemmas 3.5–3.7, and Section 2.5 of the full version.
  • Lu and Sen (2023), “Contextual Stochastic Block Model: Sharp Thresholds and Contiguity,” JMLR 24(54). See Section 5, Lemma 15, and Remark 16.
  • Mossel, Neeman, and Sly (2015), ``Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields", 162(3–4), 431–461. See Theorems 1, 2 and 3 of the journal version.
  • Mossel, Neeman, and Sly, (2018), ``A proof of the block model threshold conjecture." Combinatorica, 38(3), 665–708.
Questions for authors
  1. What is the precise new argument in the forest-parity reduction beyond the cancellation in Hopkins and Steurer’s proof of Lemma 3.7? Please distinguish the established parity principle from the additional work required for sparse typed incidences.

  2. Could the authors provide a Lean proof of the main theorem, since the primary contribution of the paper is rigorously establishing a result that is already predicted using statistical physics heuristics?

  3. In Lemma 2 and its supporting skeleton enumeration, where would a direct adaptation of the earlier path-overlap arguments fail or lose the sharp threshold constant? Please identify the indispensable new statement and explain how it resolves that obstruction. A clear answer would materially affect my assessment of the technical novelty.

  4. How much of the supercritical achievability result can be obtained from existing weighted non-backtracking theory, particularly Stephan and Massoulié (2022), after weighting graph edges by �0��0� and incidences by �1��1�? Please identify the assumptions or item-label recovery steps that prevent a direct application, if such an application is unavailable.

  5. Beyond rigorously establishing the previously predicted threshold, what additional mathematical insight does the paper provide about the capabilities or limitations of the existing proof framework? Can the authors identify or develop a substantially different proof approach, establish a fundamental limitation or sharp boundary of applicability of the established method, or uncover a previously unrecognized phenomenon within this model?

In my assessment, extending established proof machinery to another setting is insufficient specially in the age of AI, unless the extension yields substantial additional understanding. If the principal methodological contribution is the sharp typed-overlap analysis, please explain what it teaches us beyond enabling the existing framework to handle sparse incidences. In particular, does it reveal a limitation of earlier arguments, introduce a reusable new principle, or resolve an obstruction that requires a fundamentally different idea? A precise explanation would materially affect my assessment of the contribution.

References:

  • Ludovic Stephan and Laurent Massoulie, ``Non-backtracking spectra of weighted inhomogeneous ´ random graphs." Mathematical Statistics and Learning, 5(3/4):201–271, 2022.
2 comments
AuthorsOpenReview ↗

Response to Reviewer 6grE (1/2)

Thank you for your careful reading and constructive suggestions. We particularly appreciate your detailed comments on the proof structure and its connections to prior work.

Reorganization of the proof. Following your suggestions, we reorganized Sections 4–5 to make the logical dependencies and the role of each intermediate result explicit. Section 4 separates the two directions of contiguity, subcritical and critical non-recovery, and the supercritical cycle test (Lemmas 4.1–4.3 and Propositions 4.4–4.5). Section 5 begins with the matrix-to-label criterion (Lemma 12), then explains how the path means provide correlation, how path-pair moments and overlap counting control the Frobenius norm, and how color coding and rounding yield a polynomial-time estimator. We also distinguish the arguments inherited from earlier work from the estimates specific to our model.

1. Forest parity. We agree that forest-parity cancellation is not new in itself, and thank you for pointing us to Hopkins–Steurer's Lemma 3.7. We have clarified this connection in Section 5.2 and Appendix D.2. In our setting, Equation (14) gives one moment factor per repeated primitive edge, including when two paths share only one incidence of a feature wedge. The additional work is not the parity cancellation itself, but the subsequent counting and summation of these overlaps, where shared item and feature vertices have different embedding costs.

2. Lean 4. Given the time available, the uploaded archive focuses on the path-based formalization of Theorem 1. It verifies all four conclusions for the fixed-ratio Bernoulli model. For recovery, the polynomial bounds cover the counted operations and random bits given finite-precision parameter prefixes (Appendix D.8). The README provides reproduction commands, including separate checks for Equation (14) and Lemma 2.

3. What Lemma 2 adds beyond existing path arguments. We revisited Lu–Sen's proof carefully. Their analysis already accounts for partially shared feature wedges, and Appendix E shows that their fixed-composition second-moment bound can be transferred to Bernoulli incidences in the common supercritical regime with dA>1d_A>1. We therefore do not claim that partial-wedge overlaps were previously unrecognized.

The distinction is in the quantitative bound needed for our signal-weighted mixture. Two paths may have different step-type sequences, while a shared feature wedge may be only partially repeated. The proof must sum over all compatible step types without accumulating an uncontrolled multiplicative factor with the length of a shared segment. In particular, a bound that incurs an extra factor C>1C>1 at every complete shared step would yield a geometric ratio C/ΛC/\Lambda, establishing summability only when Λ>C\Lambda>C, rather than throughout Λ>1\Lambda>1.

Lemma 2 addresses this by recording each shared segment through its positions, orientation, and partial wedges. The half-wedge contributions are controlled at segment endpoints, while each paired complete step is summed over its common type with signal-dependent weights. This gives the exact limiting factor ηA2/ΛA+ηF2/ΛF=1/Λ\eta_A^2/\Lambda_A+\eta_F^2/\Lambda_F=1/\Lambda, with constants charged per segment rather than per complete step. An interior segment has O(k4)O(k^4) position records and an O(1/n)O(1/n) embedding cost; an isolated shared vertex has O(k2)O(k^2) records and the same order of cost. Equation (16) gives the resulting class-wise bound, including when dA≤1d_A\le1 and the joint signal is supercritical.

The same counting strategy also contributes to Theorem 3. Its feature-recovery achievability proof uses the overlap records and sharp weighted summation developed for Lemma 2, but requires a new estimate rather than a direct application of that lemma. With feature endpoints and m/n→0m/n\to0, item and feature identifications have different asymptotic costs. Appendix G.4.1 retains these costs separately and obtains Lemma 13, preserving the sharp complete-step factor at logarithmic depth. Thus, the overlap analysis supports both the fixed-ratio recovery proof and the new feature-recovery result.

AuthorsOpenReview ↗

Response to Reviewer 6grE (2/2)

4. What Stephan–Massoulié's method establishes. We also examined whether their weighted non-backtracking theory already gives supercritical achievability. At a fixed positive aspect ratio, it does after adapting their proof, and Appendix F now makes this connection explicit.

The adaptation involves three points. First, zero-weight padding supplies the minimum expected-degree condition, and near-matched channel weights separate the informative signal root from the remaining population spectrum and the bulk. Second, the loopless graph lacks the exact low-rank population matrix used in the spectral argument. We complete its deterministic diagonal and control the induced correction in the non-backtracking power expansion on present directed edges. Third, an informative eigenvalue on directed edges does not by itself establish recovery of item labels. Using an item-supported test vector in the proof of their Equation (8.7), while keeping the propagated population vector unchanged, gives item-side correlation that survives trimming and clipping.

We therefore agree that fixed-ratio supercritical item recovery can also be obtained through this adapted spectral approach. Our path analysis supplies a separate sharp overlap-class estimate, while Section 4 establishes the recovery converse through equality and the strict-regime testing results.

The vanishing-ratio setting is not covered by this application of the weighted spectral theorem. For instance, in the direct Bernoulli representation with m≍nαm\asymp n^\alpha, 0<α<10<\alpha<1, its sparsity parameter D=(n+m)max⁡uvPuvD=(n+m)\max_{uv}P_{uv} grows as n/m\sqrt{n/m}, outside the stated sufficient condition (log⁡D)2=o(log⁡(n+m))(\log D)^2=o(\log(n+m)). This is a limitation of applying that theorem directly, not a claim that other spectral methods cannot be developed for this regime.

5. What additional mathematical insight do we obtain? For the sparse Bernoulli JSBM, Theorem 1 turns the cavity-predicted threshold into a rigorous statistical and computational characterization, including critical non-recovery, contiguity, and polynomial-time achievability. While the proof draws on established ideas, the discrete incidence model requires controlling partially shared observations and their contributions at the sharp threshold.

Theorem 3 reveals a further, task-dependent phenomenon when m/n→0m/n\to0. The combined signal governs consistent testing and, at positive feature signal, feature weak recovery; item weak recovery, however, depends on the graph signal alone. In particular, a graph with 0<ΛA<10<\Lambda_A<1 cannot support item weak recovery even with the feature observations, yet it lowers the feature recovery threshold from 11 to 1−ΛA1-\Lambda_A.

At (ΛA,ΛF)=(0.6,0.6)(\Lambda_A,\Lambda_F)=(0.6,0.6), neither channel alone permits consistent testing, whereas their combination permits consistent testing and polynomial-time feature recovery without item weak recovery. At the mixed critical boundary ΛA+ΛF=1\Lambda_A+\Lambda_F=1, with both strengths positive, consistent testing remains possible while neither population admits weak recovery. These conclusions hold for both Bernoulli and Gaussian feature channels under the scalings in Section 6.

We recognize that recovery asymmetry at extreme aspect ratios has precedents in other models. The additional insight here is the sharp, task-specific characterization for a joint graph–feature model: graph observations can contribute to recovering feature labels even when the item labels themselves remain unrecoverable. The feature-endpoint overlap analysis in Lemma 13 provides the corresponding polynomial-time achievability proof.

We appreciate the care with which you examined both the proof and its relationship to earlier work. Your comments helped us clarify the argument, improve its organization, and state the scope of our contribution more precisely.

Reviewer_TUx5OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper establishes a sharp weak-recovery threshold for the binary joint SBM with sparse graph and item–feature relations, including critical nonrecovery and polynomial-time recovery above the threshold.

Critical strengths

A rigorous treatment of sparse relational features, including the critical case, usefully complements existing results for Gaussian covariates.

Critical weaknesses

The conceptual novelty is limited: the same model and threshold appear in Zhou et al. (2020), while the mixed-path proof framework and color-coding approach already appear in Lu and Sen (2023). The main algorithmic contribution therefore rests on the new sparse-incidence overlap estimates. Their significance relative to existing arguments is not sufficiently established, particularly given general weighted non-backtracking results.

Questions for authors
  1. Which precise step in Lu and Sen's argument fails for sparse relational features, and what substantial new idea resolves it?
  2. Why does polynomial-time recovery not follow from Stephan and Massoulié (2022), or a short extension? Channel-matched edge weights appear to give exactly the proposed spectral threshold; please identify the remaining obstacle to item-label recovery.
1 comment
AuthorsOpenReview ↗

Response to Reviewer TUx5

Thank you for your thoughtful comparison with prior work. Your questions helped us clarify the scope of the result and the role of the path analysis.

1. What carries over from Lu–Sen? Their proof already handles partially shared feature wedges. The Gaussian moment calculation does change for Bernoulli incidences. For a shared half-wedge, the Gaussian comparison factor is v+3v+3 and the Bernoulli factor is vv, where v=(m−dF)/(dFsF2)v=(m-d_F)/(d_Fs_F^2). Appendix E checks the shared-feature configurations and uses this domination to transfer Lu–Sen’s fixed-composition second-moment bound in the common supercritical regime with dA>1d_A > 1.

What Lemma 2 adds. Our estimator mixes path compositions with signal-dependent weights, so its second moment includes pairs with different step-type sequences. Lemma 2 bounds the contribution of each overlap class after summing over compatible step types. The segment records pair the complete shared steps and track partial wedges at the ends. At a shared half-wedge, the cost of identifying the feature balances the repeated-incidence moment, leaving a bounded factor at the segment end. With both channels active, summing the type of each paired complete step gives ηA2/ΛA+ηF2/ΛF=1/Λ\eta_A^2/\Lambda_A+\eta_F^2/\Lambda_F=1/\Lambda in the limit. An extra constant C>1C > 1 per complete step would give C/ΛC/\Lambda and could lose geometric summability near the threshold. Equation (16) gives the resulting class-wise bound for all fixed supercritical parameter tuples, including dA≤1d_A\le1.

2. What does Stephan–Massoulié’s method establish? Appendix F adapts their weighted non-backtracking proof to obtain supercritical item recovery at a fixed positive aspect ratio. Matched weights put the signal root outside the bulk. Nearby rational weights preserve that gap and isolate the target root. Zero-weight padding supplies the minimum expected degree. With the item channel active, we complete the population diagonal to restore low rank and control the induced correction on present directed edges. An item-supported test vector in the proof of their Equation (8.7) gives the correlation needed to turn the directed-edge eigenvector into item scores. Appendix F gives the polynomial-time construction and the trimming and clipping argument.

This gives an alternative proof of the achievability part of Theorem 1. Our statistical analysis in Section 4 establishes non-recovery through equality, mutual contiguity below the threshold, and asymptotic singularity above it.

What Theorem 3 adds. When m/n→0m/n\to0, the combined signal governs consistent testing and, for positive feature signal, feature weak recovery. Item weak recovery depends on the graph signal alone. Thus a graph with 0<ΛA<10 < \Lambda_A < 1 lowers the feature recovery threshold to 1−ΛA1-\Lambda_A, even though item weak recovery remains impossible from the joint observations. At (ΛA,ΛF)=(0.6,0.6)(\Lambda_A,\Lambda_F)=(0.6,0.6), two individually subcritical channels together permit consistent testing and polynomial-time feature recovery. At the mixed critical boundary, consistent testing remains possible and neither population admits weak recovery. These conclusions hold for both Bernoulli and Gaussian features under the scalings in Section 6.

For the feature recovery proof, we move the path endpoints to features and count item and feature identifications separately. Equation (58) gives an O(1/m)O(1/m) cost for each interior shared segment. An isolated shared vertex has the same order of cost by a separate count. The weighted sum over complete steps retains its sharp factor, giving the second-moment bound at depth O(log⁡m)O(\log m) for arbitrary vanishing ratios (Lemma 13).

Lu–Sen assume a fixed positive aspect ratio. For the direct Bernoulli weighted-graph representation with m≍nαm\asymp n^\alpha and 0<α<10 < \alpha < 1, the sparsity parameter D=(n+m)max⁡uvPuvD=(n+m)\max_{uv} P_{uv} grows as n/m\sqrt{n/m}. This example falls outside the sufficient regime (log⁡D)2=o(log⁡(n+m))(\log D)^2=o(\log(n+m)) used by Stephan–Massoulié’s spectral theorem.

Thank you again for your suggestions. We hope the revised exposition addresses your concerns and would be happy to discuss any remaining questions.

Reviewer_e6JpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors present a variant of the two-community stochastic block model recovery problem. In this variant, each vertex has mm binary features, where m grows proportionally to nn. The feature vector is sparse, in the sense that the expected number of 1's remain bounded as mm tends to infinity. By viewing each feature as a vertex and connecting each vertex to its positive features, the feature vectors can be represented by a sparse bipartite graph. This paper shows that the signal of this SBM with features is the signal of the SBM plus the signal of the bipartite graph. The authors prove that recovery is possible whenever this combined signal exceeds 1, while it is impossible when this signal is 1 or smaller.

Critical strengths

I like that this paper presents one clean main result.

I also did not find any gap in the proof.

Critical weaknesses

While the main result is clean, it is also rather limited. Many potential extensions like size imbalance and degree heterogeneity (both for the SBM graph and the bipartite feature graph) are not discussed. The interesting extension to multiple communities is only mentioned in a single phrase, without discussion. (Almost) exact recovery is also not mentioned.

Many central concepts are not explained. For example: forest parity, typed vertex counting, Kesten Stigum matrix. I'm sure these concepts exist in the literature, but you do not explain them or refer to them. You are assuming your reader is already rather deep into the SBM literature. It would be nice if the paper is a bit more self-contained.

The "Related works" section is mainly just a list of references and does not properly explain the relation of the papers to the present work. For example, Florescu & Perkins seems to be very closely related to the case dA=0d_A=0. Also, Chatterjee et al. prove a similar sum of sparse signals result, where recovery of the joint model is possible when recovery of each signal channel is impossible. You could use this overview to introduce the central concepts that are used further in the paper.

The paper is written in an unpleasant style, possibly due to heavy use of LLMs. Some examples of what made reading difficult:

  • The paragraph "Key mechanism" (Lines 102-105) is very dense and refers to many concepts that have not been introduced.
  • Phrases like "exact second-moment identity" (line 114) and "exact identity" (line 299) sound like other identities in the paper are inexact.
  • Lemma 2 bounds a quantity that is only defined in words. In general, section 4 reads like a long computation where the most central steps are being made in prose.
  • "Both coefficients are of order mm at fixed nonzero sFs_F" (line 216) what coefficients?
  • dP/dQd\mathbb P/ d\mathbb Q (line 357) is not introduced. I'm guessing this is the likelihood ratio? But is this the likelihood ratio of the branching process or the entire graph?

After reading the paper, it is still unclear to me for what version of belief propagation weak recovery is proven. Make the algorithm explicit.

Questions for authors

For what belief-propagation variant do you prove weak recovery?

Can we extend this result to multiple and/or imbalanced communities? Which part of the proof would break?

I'm guessing we could extend the result to replace the single SBM by a multilayer of sparse SBMs, since their signals also add up. Is this possible, or am I missing something?

What if n,m→∞n,m\to\infty at different speeds?

2 comments
AuthorsOpenReview ↗

Response to Reviewer e6Jp

Thank you for your careful reading and for encouraging us to clarify the proof and discuss the scope of the model. Your question about different growth rates led us to develop Theorem 3.

Belief propagation. We do not prove weak recovery for any belief-propagation (BP) variant. Theorem 1 proves weak recovery above the threshold for the self-avoiding-path estimator in Section 5.4. Damped BP is used only in the numerical experiments (Section 7 and Appendix H). The path estimator uses color coding and a subset dynamic program to compute the matrix, then SDP projection and Gaussian rounding to return item labels.

Making the proof easier to follow. Section 2.1 now builds the Kesten–Stigum matrix from neighbor counts and squared edge correlations. In Section 4, dP/dQdP/dQ is the likelihood ratio for the full observation (A,F)(A,F). We state the contiguity and posterior-pair arguments separately. Equation (12) identifies the constant and label-dependent coefficients of the incidence second moment. The explanation following Equation (14) shows why the forest parity argument removes the label-dependent terms. Equation (15) works through the item and feature identification costs, and Section 5.3 now defines the sum that Lemma 2 bounds.

The two related-work comparisons. When the item graph is removed, the model is a bipartite SBM. We now relate its signal scale to Florescu–Perkins' small-side threshold in the unbalanced regime (Section 2). Section 3 explains how Chatterjee–Nandy–Sadhu combine graph layers that share item labels with a Gaussian covariate signal. Our auxiliary observations are sparse incidences to features with their own latent labels. Section 5.2 illustrates the resulting overlap issue with two paths that share just one incidence.

Unequal proportions, more communities, and degree heterogeneity. For two communities with unequal proportions, guessing the majority label already gives nonzero overlap under our current definition. An extension needs a recovery criterion that accounts for that baseline. The odd sign moments can also be nonzero, so the cancellation in Equation (14) needs a new argument. With more communities, the converse at the threshold requires analyzing the full broadcast recursion, since Proposition 4.4 uses binary symmetry. With degree heterogeneity, arriving along a graph edge or a feature incidence can bias the degree distribution differently. The propagation matrix in Section 2.1 would then need the size-biased neighbor counts for each edge type. Section 8 outlines these directions. We leave sharp thresholds for these models to future work. At the fixed degrees of Theorem 1, a positive fraction of items are isolated, which precludes almost-exact and exact recovery.

Does the signal add across graph layers? Yes at the level of the complete-step sum when the layers share item labels and are independent conditional on them. Each layer adds dℓsℓ2d_\ell s_\ell^2. In extending the path calculation, a repeated observation must be identified by both the item pair and the layer. Two paths using the same pair in different layers share vertices. Their edge observations are independent conditional on the labels. Section 8 explains the additive step calculation. Extending the overlap, testing, and converse arguments to obtain a full multilayer theorem is future work.

What changes when nn and mm grow at different rates? Theorem 3 (Section 6) treats m/n→0m/n\to0 with both populations growing and fixed item graph parameters. We scale the Bernoulli baseline as qF=c/nmq_F=c/\sqrt{nm} and the Gaussian signal as an2=κ/nma_n^2=\kappa/\sqrt{nm}, keeping the respective feature strengths c2sF4c^2s_F^4 and κ2\kappa^2 fixed. The three sharp conditions are ΛA+ΛF≥1\Lambda_A+\Lambda_F\ge1 for consistent testing, ΛA>1\Lambda_A > 1 for item weak recovery, and ΛA+ΛF>1\Lambda_A+\Lambda_F > 1 for feature weak recovery when ΛF>0\Lambda_F > 0. Above its threshold, feature recovery is achievable in randomized polynomial time. At (ΛA,ΛF)=(0.6,0.6)(\Lambda_A,\Lambda_F)=(0.6,0.6), combining the channels enables testing and feature recovery while item recovery remains impossible. At the mixed critical boundary, testing is still consistent and weak recovery fails on both sides (Appendix G).

Thank you again for your suggestions. We hope the revised exposition addresses your concerns and would be happy to discuss any remaining questions.

I appreciate the authors thorough responses. However, so much has been changed between the original and the revised manuscript, that it would require an entire new reading to check. This is simply not feasible in this short discussion period with the amount of reviews that have been assigned. Therefore, I will keep my rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.