# Community detection in censored hypergraph

arXiv: https://arxiv.org/abs/2111.03179 · HTML: https://mlsanity.com/paper/2111.03179/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 4 Nov 2021.

## Builds on (most cited first, 17 of 17)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection](https://mlsanity.com/paper/2009.05870/) (2020)
- [Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery](https://mlsanity.com/paper/1404.4749/) (2014)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Community detection with nodal information](https://mlsanity.com/paper/1610.09735/) (2016)
- [Community Detection with Dependent Connectivity](https://mlsanity.com/paper/1812.06406/) (2018)

## Built on by (most cited first, 1 of 1)

- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)

## Abstract (arXiv)

Community detection refers to the problem of clustering the nodes of a network (either graph or hypergrah) into groups. Various algorithms are available for community detection and all these methods apply to uncensored networks. In practice, a network may has censored (or missing) values and it is shown that censored values have non-negligible effect on the structural properties of a network. In this paper, we study community detection in censored m-uniform hypergraph from information-theoretic point of view. We derive the information-theoretic threshold for exact recovery of the community structure. Besides, we propose a polynomial-time algorithm to exactly recover the community structure up to the threshold. The proposed algorithm consists of a spectral algorithm plus a refinement step. It is also interesting to study whether a single spectral algorithm without refinement achieves the threshold. To this end, we also explore the semi-definite relaxation algorithm and analyze its performance.