mlsanityData to 14 Oct 2026

Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

arXiv 2011.09841 ↗First posted 15 Nov 2020cs.SI cs.LG math.STcited by 22

Not on the map. Why?

Abstract (arXiv)

We study community detection in the contextual stochastic block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596 [cs.SI], the second author studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous cavity method from statistical physics, they conjectured the sharp limits for community detection in this setting. Further, the information theoretic threshold was verified, assuming that the average degree of the observed graph is large. It is expected that the conjecture holds as soon as the average degree exceeds one, so that the graph has a giant component. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 3; 2024: 7; 2025: 1; 2026: 4.

22 papers.

Sort:

  1. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  2. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  3. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  4. 2022Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graphcited by 14
  5. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  6. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 12
  7. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  8. 2021An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guaranteescited by 10
  9. 2022Exact Community Recovery in Correlated Stochastic Block Modelscited by 8
  10. 2024Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block modelscited by 7
  11. 2023Neural-prior stochastic block modelcited by 4
  12. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
10 more
  1. 2024Analysis of Corrected Graph Convolutionscited by 2
  2. 2024LinkThief: Combining Generalized Structure Knowledge with Node Similarity for Link Stealing Attack against GNNcited by 2
  3. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2
  4. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  5. 2026Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Modelscited by 2
  6. 2022Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Thresholdcited by 0
  7. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  8. 2026A Spectral Theory of Normalized Corrected GNN Propagationcited by 0
  9. 2026The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomycited by 0
  10. 2026HoTS: Homophily-Aware Temperature Scaling for Graph Neural Network Calibrationcited by 0