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

We study community detection in the binary symmetric joint stochastic block model (JSBM), which couples a sparse graph on $n$ items to a sparse item–feature relation with $m$ 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 $d_A,d_F$ denote the mean graph and item-side incidence degrees, $s_A,s_F$ the corresponding one-edge label correlations, and $m/n\to \gamma$. For fixed known parameters away from criticality, we prove the sharp threshold $\Lambda :=d_A{s}_A^2+\frac{d_F^2{s}_F^4}{\gamma }=1$. For $\Lambda <1$, the planted and null laws are mutually contiguous and weak recovery is impossible; for $\Lambda >1$, 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.