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 d4 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 Gaudio and Joshi (2023a).

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\ge 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 Gaudio and Joshi (2023a). } }
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\ge 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 Gaudio and Joshi (2023a).
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