- 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 ( {}) comes from a sparse item–item graph $A = (A_{ij}:i,j\in [n]) $ and a sparse item–feature graph with latent item and feature labels {} and {} respectively. For fixed known parameters involving average degrees , edge label correlations , and , the authors establish the sharp weak-recovery threshold at . They show that weak recovery is impossible for and achievable in randomized polynomial time for . Moreover, they prove mutual contiguity of the planted () and degree-matched null observation () laws strictly below the threshold () and asymptotic singularity strictly above it ().
In the subcritical case (), the proof of goes via proving uniform boundedness of the second moment of the likelihood-ratio under the null . The proof of goes through analysing typed-cycle statistics and establishing distributional convergence of under the null to a strictly positive random variable with mean one. A computation similar to obtained by fixing finitely many item labels establishes impossibility of weak recovery. In the critical case (), they establish information contraction on the two-type broadcast tree and transfer non-reconstruction to the graph.
In the supercritical case (), weighted centered typed-cycle statistics provide use a natural hypothesis test that establishes asymptotic singularity . More precisely, it shows that . 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
- 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.
- 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 , the result that under implying and the related one on uniform boundedness of the limit of showing 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 . 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 (), 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
-
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.
-
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?
-
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.
-
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 and incidences by ? Please identify the assumptions or item-label recovery steps that prevent a direct application, if such an application is unavailable.
-
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
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 , , its sparsity parameter grows as , outside the stated sufficient condition . 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 . 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 cannot support item weak recovery even with the feature observations, yet it lowers the feature recovery threshold from to .
At , 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 , 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.
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>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>1 at every complete shared step would yield a geometric ratio C/Λ, establishing summability only when Λ>C, rather than throughout Λ>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/Λ, with constants charged per segment rather than per complete step. An interior segment has O(k4) position records and an O(1/n) embedding cost; an isolated shared vertex has O(k2) records and the same order of cost. Equation (16) gives the resulting class-wise bound, including when dA≤1 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→0, 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.