Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Preprint
Abstract
Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^δ$. The projection of a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to some hyperedge. The goal is to reconstruct the hypergraph given its projection. An earlier work of Bresler, Guo, and Polyanskiy (COLT 2024) showed that exact recovery for $d=3$ is possible if and only if $δ< 2/5$. This work completely resolves the question for all values of $d$ for both exact and partial recovery and for both cases of whether multiplicity information about each edge is available or not. In addition, we show that the reconstruction fidelity undergoes an all-or-nothing transition at a threshold. In particular, this resolves all conjectures from Bresler, Guo, and Polyanskiy (COLT 2024).
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block ModelThe Annals of Statistics, 2026
- Hypergraph reconstruction from uncertain pairwise observationsScientific Reports, 2023
- Settling the Sharp Reconstruction Thresholds of Random Graph MatchingIEEE Transactions on Information Theory, 2022
- Hypergraph reconstruction from network dataCommunications Physics, 2021
- Phase transitions for detecting latent geometry in random graphsProbability Theory and Related Fields, 2020
- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration2013
- Hiding Quiet Solutions in Random Constraint Satisfaction ProblemsPhysical Review Letters, 2009