mlsanityData to 7 Oct 2026

Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach

arXiv 1807.02884 ↗First posted 8 Jul 2018math.PR cs.IT cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

We study the problem of community detection in a random hypergraph model which we call the stochastic block model for k-uniform hypergraphs (k-SBM). We investigate the exact recovery problem in k-SBM and show that a sharp phase transition occurs around a threshold: below the threshold it is impossible to recover the communities with non-vanishing probability, yet above the threshold there is an estimator which recovers the communities almost asymptotically surely. We also consider a simple, efficient algorithm for the exact recovery problem which is based on a semidefinite relaxation technique.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 7; 2022: 4; 2023: 2; 2024: 5; 2025: 2.

20 papers.

Sort:

  1. 2021Generative hypergraph clustering: from blockmodels to modularitycited by 48
  2. 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
  3. 2021Latent Space Model for Higher-order Networks and Generalized Tensor Decompositioncited by 13
  4. 2022Hypergraph Artificial Benchmark for Community Detection (h-ABCD)cited by 9
  5. 2024HYGENE: A Diffusion-based Hypergraph Generation Methodcited by 8
  6. 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
  7. 2022Sparse random hypergraphs: Non-backtracking spectra and community detectioncited by 5
  8. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
  9. 2022Multiway Spherical Clustering via Degree-Corrected Tensor Block Modelscited by 4
  10. 2021Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detectioncited by 2
  11. 2022Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrixcited by 2
  12. 2023Multilayer hypergraph clustering using the aggregate similarity matrixcited by 2
8 more
  1. 2021Community detection in censored hypergraphcited by 1
  2. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 1
  3. 2024Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Modelscited by 1
  4. 2024Hypergraph clustering using Ricci curvature: an edge transport perspectivecited by 1
  5. 2024Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithmscited by 0
  6. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  7. 2025Feature-Aware (Hyper)graph Generation via Next-Scale Predictioncited by 0
  8. 2025Hypergraph Contrastive Learning for both Homophilic and Heterophilic Hypergraphscited by 0