Statistical and Computational Limits of Single-Community Search with Side Information in Stochastic Block Models

Ray, Sanghavi and Shakkottai (2018) introduced the semi-supervised search problem — recovering a single target community in a stochastic block model (SBM) using non-graph side information such as a small set of labeled nodes — and posed three open directions: (A) the fundamental (phase-transition) limits of community detection with non-trivial side information such as $\Theta(\log n)$ labeled nodes in a community, (B) richer side-information models beyond scalar biased node weights together with corresponding problem definitions beyond search, and (C) faster local or belief-propagation algorithms for the semi-supervised setting. In the 2015–2025 literature, exact-recovery thresholds with side information are now characterized for the two-block SBM (where $\Theta(\log n)$-scale label revelation provably does not move the threshold), for the one-community model at logarithmic average degree (including its belief-propagation phase transition and a local-algorithm converse), and for the general node-attributed SBM via a Chernoff–Hellinger criterion with optimal spectral algorithms; the richer-side-information direction has materialized as the contextual SBM program with sharp thresholds. What remains open is the regime the source paper itself targeted: the sharp characterization of the minimal seed budget for recovering a target community among $k \ge 3$ communities in sparse regimes ($p = \Theta(\log n / n^{\epsilon})$, community sizes from $\sqrt{n}$ to $n/k$), where the known algorithm requires $\tilde{\Omega}(n^{\epsilon/2})$ labeled nodes, no matching lower bound exists, and the computational-statistical tradeoffs of local and message-passing search with side information are unquantified.

Background

Community detection is the task of inferring latent group structure from a graph. Its canonical generative model is the stochastic block model (SBM): $n$ vertices are partitioned into $k$ non-overlapping communities $V_1,\dots,V_k$, and an edge between two vertices appears independently with probability $p$ if both lie in the same community and $q < p$ otherwise. Recovery goals are stratified: exact recovery requires reconstructing the entire partition (up to a global relabeling) with probability tending to one as $n$ grows, while weak (partial) recovery requires misclassifying only a vanishing fraction of nodes. In the symmetric two-block SBM with $p = a\log n/n$ and $q = b\log n/n$, exact recovery is possible if and only if $\frac{a+b}{2}-\sqrt{ab} > 1$, equivalently $(\sqrt{a}-\sqrt{b})^2 > 2$ (Abbe, Bandeira and Hall, 2016). Sharp thresholds of this kind — separating information-theoretically possible from impossible recovery — are what the field calls its fundamental limits.

Most of this theory treats the fully unsupervised problem, where the algorithm sees only the graph. Ray, Sanghavi and Shakkottai (2018) studied instead the search problem: recover just one designated target community $V_1$ out of the $k$ communities, using side information, i.e. non-graph data correlated with membership in $V_1$. Because $V_1$ is designated, its recovery carries no global relabeling ambiguity: exact recovery of $V_1$ means $\hat V_1 = V_1$ with probability tending to one, and weak (partial) recovery of $V_1$ means misclassifying only $o(|V_1|)$ of its members. Their side-information model gives every node $j$ a random weight $w_j$ satisfying $\mathbb{E}[w_j \mid j \in V_1] > \mathbb{E}[w_j \mid j \in V_i]$ for $i \ne 1$ (a biased node weight). A canonical way to produce such weights is to reveal a small set $L \subset V_1$ of labeled nodes (seeds) and count shared neighborhoods with $L$. Their Community Search algorithm, a weighted variant of the method of moments (a classical estimation technique that matches empirical moments to their population values), recovers $V_1$ partially, and exactly after a degree-thresholding post-processing step, under an identifiability condition on $p-q$ comparable to standard community-detection thresholds. Notably, in the sparse regime $p = \Theta(\log n/n^{\epsilon})$ with $\epsilon \in [1/2,1]$, their weight construction requires $L = \tilde{\Omega}(n^{\epsilon/2})$ labeled nodes — far above the $\Theta(\log n)$ scale the authors single out as emblematic of non-trivial side information; whether a logarithmic seed budget actually suffices for recovery in this regime, information-theoretically or computationally, is not known. Without side information, the single-community problem is well understood for a community of size $K = o(n)$: Montanari (2015) located the weak-recovery threshold for finding one community in a sparse graph — a Kesten–Stigum-type boundary, the Kesten–Stigum threshold being the classical spectral limit for recovering planted partitions — and Hajek, Wu and Xu (2017) characterized the information limits for recovering a hidden community.

Side information itself comes in several strengths: noisy labels (each node's label observed through a binary symmetric channel that flips it with some probability), partially revealed labels (an erasure channel; revealing $\Theta(\log n)$ seeds out of $n$ nodes is a vanishing revealed fraction), and node attributes or covariates (the contextual SBM, in which each node carries a random feature vector whose distribution depends on its community). On the algorithmic side, belief propagation (BP) is an iterative message-passing method that computes approximate posterior marginals over the graph, and local algorithms are those restricted to bounded-radius neighborhoods. A substantial 2015–2025 literature has characterized what side information does to SBM thresholds in specific regimes: two-block exact recovery with noisy and partially revealed labels (Saad and Nosratinia), the one-community model with side information at logarithmic average degree including its BP phase transition (Saad and Nosratinia), the general node-attributed SBM (Dreveton, Fernandes and Figueiredo), and the contextual SBM (Deshpande, Montanari, Mossel and Sen; Lu and Sen; Duranthon and Zdeborová). What is not settled is the regime the source paper itself targeted: sparse graphs with many or small communities, where exact recovery is impossible without side information and the value of a vanishing, logarithmic-scale seed budget — for both the information-theoretic threshold and the power of efficient local and message-passing algorithms — remains unquantified.

Problem Statement

The problem is to complete the theory of semi-supervised single-community search in stochastic block models — the program posed by Ray, Sanghavi and Shakkottai (2018) — with three linked components, all of which are required for a complete resolution:

1. Information-theoretic limits with labeled-node side information. For an $(n,k,p,q)$ SBM with target community $V_1$ and $L$ labeled nodes revealed from $V_1$ (or, more generally, node weights or attributes whose distributions depend on membership in $V_1$), characterize with matching necessary and sufficient conditions the thresholds for exact and partial recovery of $V_1$ as functions of the model parameters ($n$, $k$, $p$, $q$ and the community-size profile), of the side-information channel parameters — the bias and concentration of the node weights for the required labeled-node channel, with a label-noise probability, a revealed-label fraction and attribute distributions admissible as extensions rather than each being separately mandatory — and of the seed budget $L$. The emblematic instance is the question the source paper singles out: what does a $\Theta(\log n)$-sized labeled set in the target community buy? In the sparse search regime $p = \Theta(\log n/n^{\epsilon})$, $\epsilon \in [1/2,1]$, with community sizes ranging from $\Omega(\sqrt{n})$ to $n/k$, determine the minimal seed budgets $L^*$ for exact recovery and for weak (partial) recovery of the target community, noting that the source's algorithm requires $\tilde{\Omega}(n^{\epsilon/2})$ seeds and no matching lower bound is known. The general parameter-dependent characterization is required, and the emblematic sparse-regime question is a required instance of it rather than a substitute for it, so resolving the minimal seed budgets $L^*$ alone does not complete this component.

2. Richer side information and formulations beyond search. Extend the scalar biased-weight framework to structured side-information channels — vector-valued node attributes or features, multiple labels or observations per node, noisy and partially revealed labels — and characterize, for at least one such channel, the recovery thresholds within the same search model, as distinct from the two-block, one-community logarithmic-degree, node-attributed and contextual settings already characterized (see Background). Beyond search, the source's direction (B) also covers corresponding problem definitions such as parallel semi-supervised graph clustering: given a small number of labeled nodes from every community, recover all communities by applying the community search to each target community, in parallel — a formulation the source paper states its algorithm naturally provides and evaluates empirically. The parallel semi-supervised graph clustering formulation is the required beyond-search deliverable of this component, not illustrative context: its recovery guarantees must be characterized alongside the structured side-information channels above. Threshold characterizations for multi-community semi-supervised recovery exist in other regimes (a Chernoff–Hellinger criterion with a noisy label oracle for node-attributed SBMs with a constant number of blocks at logarithmic average degree, Dreveton, Fernandes and Figueiredo 2023; an SNR threshold with a local-algorithm converse for weak recovery in partially labeled $k$-block SBMs, Cai, Liang and Rakhlin 2016), but none of these covers the sparse search regime above with a few labeled seeds per community.

3. Efficient algorithms and computational-statistical tradeoffs. Determine whether local algorithms and message-passing methods (belief propagation) that incorporate the side information achieve the information-theoretic limits above in the sparse search regime, and quantify the tradeoff among statistical accuracy, seed budget, and computation time, the motivation being that search of one community should be possible faster than full graph clustering.

References

1. Avik Ray, Sujay Sanghavi, Sanjay Shakkottai. Searching for a Single Community in a Graph. arXiv:1806.07944 (2018); journal version in ACM Transactions on Modeling and Performance Evaluation of Computing Systems, DOI 10.1145/3200863. https://arxiv.org/abs/1806.07944
2. Hussein Saad, Aria Nosratinia. Community Detection with Side Information: Exact Recovery under the Stochastic Block Model. arXiv:1805.08901 (2018); IEEE Journal of Selected Topics in Signal Processing, DOI 10.1109/JSTSP.2018.2834874. https://arxiv.org/abs/1805.08901
3. Hussein Saad, Ahmed Abotabl, Aria Nosratinia. Side Information in the Binary Stochastic Block Model: Exact Recovery. arXiv:1708.04972 (2017; withdrawn by the authors due to errors, superseded by later corrected works). https://arxiv.org/abs/1708.04972
4. Hussein Saad, Aria Nosratinia. Recovering a Single Community with Side Information. arXiv:1809.01738 (2018); IEEE Transactions on Information Theory, DOI 10.1109/TIT.2020.3030764 (2020). https://arxiv.org/abs/1809.01738
5. Jin Sima, Feng Zhao, Shao-Lun Huang. Exact Recovery in the Balanced Stochastic Block Model with Side Information. IEEE Information Theory Workshop (ITW) 2021, DOI 10.1109/ITW48936.2021.9611438. https://doi.org/10.1109/ITW48936.2021.9611438
6. Feng Zhao, Jin Sima, Shao-Lun Huang. On the Optimal Error Rate of Stochastic Block Model with Symmetric Side Information. IEEE Information Theory Workshop (ITW) 2021, DOI 10.1109/ITW48936.2021.9611481. https://doi.org/10.1109/ITW48936.2021.9611481
7. Clara Stegehuis, Laurent Massoulié. Efficient inference in stochastic block models with vertex labels. arXiv:1806.07562 (2018). https://arxiv.org/abs/1806.07562
8. Elchanan Mossel, Jiaming Xu. Local Algorithms for Block Models with Side Information. arXiv:1508.02344 (2015); ITCS 2016. https://arxiv.org/abs/1508.02344
9. T. Tony Cai, Tengyuan Liang, Alexander Rakhlin. Inference via Message Passing on Partially Labeled Stochastic Block Models. arXiv:1603.06923 (2016). https://arxiv.org/abs/1603.06923
10. Yash Deshpande, Andrea Montanari, Elchanan Mossel, Subhabrata Sen. Contextual Stochastic Block Models. arXiv:1807.09596 (2018). https://arxiv.org/abs/1807.09596
11. Chen Lu, Subhabrata Sen. Contextual Stochastic Block Model: Sharp Thresholds and Contiguity. arXiv:2011.09841 (2020). https://arxiv.org/abs/2011.09841
12. O. Duranthon, L. Zdeborová. Optimal Inference in Contextual Stochastic Block Models. arXiv:2306.07948 (2023). https://arxiv.org/abs/2306.07948
13. Hugo Cui, Luca Saglietti, Lenka Zdeborová. Large Deviations of Semi-supervised Learning in the Stochastic Block Model. arXiv:2108.00847 (2021). https://arxiv.org/abs/2108.00847
14. Maximilien Dreveton, Felipe S. Fernandes, Daniel R. Figueiredo. Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model. arXiv:2310.19854 (2023). https://arxiv.org/abs/2310.19854
15. Julia Gaudio, Nirmit Joshi. Exact Community Recovery under Side Information: Optimality of Spectral Algorithms. arXiv:2406.13075 (2024); ICLR 2025. https://arxiv.org/abs/2406.13075
16. Bruce Hajek, Yihong Wu, Jiaming Xu. Information Limits for Recovering a Hidden Community. IEEE Transactions on Information Theory, DOI 10.1109/TIT.2017.2653804 (2017). https://doi.org/10.1109/TIT.2017.2653804
17. Andrea Montanari. Finding One Community in a Sparse Graph. Journal of Statistical Physics, DOI 10.1007/s10955-015-1338-2 (2015). https://doi.org/10.1007/s10955-015-1338-2
18. Emmanuel Abbe, Afonso S. Bandeira, Georgina Hall. Exact Recovery in the Stochastic Block Model. IEEE Transactions on Information Theory, DOI 10.1109/TIT.2015.2490670 (2016). https://doi.org/10.1109/TIT.2015.2490670
19. Konstantin Avrachenkov, Maximilien Dreveton. Almost exact recovery in noisy semi-supervised learning. arXiv:2007.14717 (2020). https://arxiv.org/abs/2007.14717
20. Martijn Gösgens, Maximilien Dreveton. Recovering Small Communities in the Planted Partition Model. arXiv:2504.01663 (2025). https://arxiv.org/abs/2504.01663
21. Aaradhya Pandey, Sanjeev Kulkarni. Exact recovery in Gaussian weighted stochastic block model and planted dense subgraphs: Statistical and algorithmic thresholds. arXiv:2402.12515 (2024). https://arxiv.org/abs/2402.12515