Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915907168632832 |
|---|---|
| author | Gong, Shuyang Li, Zhangsong Xu, Qiheng |
| author_facet | Gong, Shuyang Li, Zhangsong Xu, Qiheng |
| contents | For a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is $n^{δ+o(1)}$, the projection of such a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to a same hyperedge. In this work, we study the inference problem where the observation is a \emph{noisy} version of the graph projection where each edge in the projection is kept with probability $p=n^{-1+α+o(1)}$ and each edge not in the projection is added with probability $q=n^{-1+β+o(1)}$. For all constant $d$, we establish sharp thresholds for both detection (distinguishing the noisy projection from an Erdős-Rényi random graph with edge density $q$) and reconstruction (estimating the original hypergraph). Notably, our results reveal a \emph{detection-reconstruction gap} phenomenon in this problem. Our work also answers a problem raised in \cite{BGPY25+}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17527 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection Gong, Shuyang Li, Zhangsong Xu, Qiheng Statistics Theory Combinatorics Probability For a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is $n^{δ+o(1)}$, the projection of such a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to a same hyperedge. In this work, we study the inference problem where the observation is a \emph{noisy} version of the graph projection where each edge in the projection is kept with probability $p=n^{-1+α+o(1)}$ and each edge not in the projection is added with probability $q=n^{-1+β+o(1)}$. For all constant $d$, we establish sharp thresholds for both detection (distinguishing the noisy projection from an Erdős-Rényi random graph with edge density $q$) and reconstruction (estimating the original hypergraph). Notably, our results reveal a \emph{detection-reconstruction gap} phenomenon in this problem. Our work also answers a problem raised in \cite{BGPY25+}. |
| title | Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection |
| topic | Statistics Theory Combinatorics Probability |
| url | https://arxiv.org/abs/2506.17527 |