Thresholds for Reconstruction of Random Hypergraphs From Graph Projections

Guy Bresler, Chenghao Guo, Yury Polyanskiy
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:632-647, 2024.

Abstract

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\geq 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. A consequence of our results is that claims from the 2023 COLT paper gaudio’23 are disproved.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-bresler24a, title = {Thresholds for Reconstruction of Random Hypergraphs From Graph Projections}, author = {Bresler, Guy and Guo, Chenghao and Polyanskiy, Yury}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {632--647}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/bresler24a/bresler24a.pdf}, url = {https://proceedings.mlr.press/v247/bresler24a.html}, abstract = {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\geq 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. A consequence of our results is that claims from the 2023 COLT paper gaudio’23 are disproved. } }
Endnote
%0 Conference Paper %T Thresholds for Reconstruction of Random Hypergraphs From Graph Projections %A Guy Bresler %A Chenghao Guo %A Yury Polyanskiy %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-bresler24a %I PMLR %P 632--647 %U https://proceedings.mlr.press/v247/bresler24a.html %V 247 %X 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\geq 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. A consequence of our results is that claims from the 2023 COLT paper gaudio’23 are disproved.
APA
Bresler, G., Guo, C. & Polyanskiy, Y.. (2024). Thresholds for Reconstruction of Random Hypergraphs From Graph Projections. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:632-647 Available from https://proceedings.mlr.press/v247/bresler24a.html.

Related Material