Planted Bipartite Graph Detection
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914703758852096 |
|---|---|
| author | Rotenberg, Asaf Huleihel, Wasim Shayevitz, Ofer |
| author_facet | Rotenberg, Asaf Huleihel, Wasim Shayevitz, Ofer |
| contents | We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over $n$ vertices with edge density $q$. Under the alternative, there exists a planted $k_{\mathsf{R}} \times k_{\mathsf{L}}$ bipartite subgraph with edge density $p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where $p,q = Θ\left(1\right)$, and the sparse regime where $p,q = Θ\left(n^{-α}\right), α\in \left(0,2\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03658 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Planted Bipartite Graph Detection Rotenberg, Asaf Huleihel, Wasim Shayevitz, Ofer Data Structures and Algorithms Information Theory Machine Learning Statistics Theory We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over $n$ vertices with edge density $q$. Under the alternative, there exists a planted $k_{\mathsf{R}} \times k_{\mathsf{L}}$ bipartite subgraph with edge density $p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where $p,q = Θ\left(1\right)$, and the sparse regime where $p,q = Θ\left(n^{-α}\right), α\in \left(0,2\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region. |
| title | Planted Bipartite Graph Detection |
| topic | Data Structures and Algorithms Information Theory Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2302.03658 |