Partial and Exact Recovery of a Random Hypergraph from its Graph Projection

Guy Bresler, Chenghao Guo, Yury Polyanskiy, Andrew Yao
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:534-593, 2025.

Abstract

Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^\delta$. 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 $\delta < 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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-bresler25a, title = {Partial and Exact Recovery of a Random Hypergraph from its Graph Projection}, author = {Bresler, Guy and Guo, Chenghao and Polyanskiy, Yury and Yao, Andrew}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {534--593}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/bresler25a/bresler25a.pdf}, url = {https://proceedings.mlr.press/v291/bresler25a.html}, abstract = {Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^\delta$. 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 $\delta < 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).} }
Endnote
%0 Conference Paper %T Partial and Exact Recovery of a Random Hypergraph from its Graph Projection %A Guy Bresler %A Chenghao Guo %A Yury Polyanskiy %A Andrew Yao %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-bresler25a %I PMLR %P 534--593 %U https://proceedings.mlr.press/v291/bresler25a.html %V 291 %X Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^\delta$. 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 $\delta < 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).
APA
Bresler, G., Guo, C., Polyanskiy, Y. & Yao, A.. (2025). Partial and Exact Recovery of a Random Hypergraph from its Graph Projection. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:534-593 Available from https://proceedings.mlr.press/v291/bresler25a.html.

Related Material