Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918364198207488 |
|---|---|
| author | Morgan, Alexander Guo, Chenghao |
| author_facet | Morgan, Alexander Guo, Chenghao |
| contents | We formulate and analyze a heterogeneous random hypergraph model, and we provide an achieveability result for recovery of hyperedges from the observed projected graph. We observe a projected graph which combines random hyperedges across all degrees, where a projected edge appears if and only if both vertices appear in at least one hyperedge. Our goal is to reconstruct the original set of hyperedges of degree $d_j$ for some $j$. Our achievability result is based on the idea of selecting maximal cliques of size $d_j$ in the projected graph, and we show that this algorithm succeeds under a natural condition on the densities. This achievability condition generalizes a known threshold for $d$-uniform hypergraphs with noiseless and noisy projections. We conjecture the threshold to be optimal for recovering hyperedges with the largest degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01268 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection Morgan, Alexander Guo, Chenghao Data Structures and Algorithms Information Theory Probability Statistics Theory We formulate and analyze a heterogeneous random hypergraph model, and we provide an achieveability result for recovery of hyperedges from the observed projected graph. We observe a projected graph which combines random hyperedges across all degrees, where a projected edge appears if and only if both vertices appear in at least one hyperedge. Our goal is to reconstruct the original set of hyperedges of degree $d_j$ for some $j$. Our achievability result is based on the idea of selecting maximal cliques of size $d_j$ in the projected graph, and we show that this algorithm succeeds under a natural condition on the densities. This achievability condition generalizes a known threshold for $d$-uniform hypergraphs with noiseless and noisy projections. We conjecture the threshold to be optimal for recovering hyperedges with the largest degree. |
| title | Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection |
| topic | Data Structures and Algorithms Information Theory Probability Statistics Theory |
| url | https://arxiv.org/abs/2603.01268 |