2025/02/12 by Bresler, Guy, Guo, Chenghao, Polyanskiy, Yury
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2502.08840
The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem of reconstructing a random d-uniform hypergraph from its projection. Feasibility of this task depends on d and the density of hyperedges in the random hypergraph. For d=3 we precisely determine the threshold, while for d≥ 4 we give bounds. All of our feasibility results are obtained by exhibiting an efficient algorithm for reconstructing the original hypergraph, while infeasibility is information-theoretic. Our results also apply to mildly inhomogeneous random hypergrahps, including hypergraph stochastic block models (HSBM). A consequence of our results is an optimal HSBM recovery algorithm, improving on a result of Guadio and Joshi in 2023.