Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
Abstract
We consider two closely related problems: planted clustering and submatrix localization. In the planted clustering problem, a random graph is generated based on an underlying cluster structure of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and the stochastic block model, which are widely used for studying community detection, graph clustering and bi-clustering.
Cite
Text
Chen and Xu. "Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices." Journal of Machine Learning Research, 2016.Markdown
[Chen and Xu. "Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices." Journal of Machine Learning Research, 2016.](https://mlanthology.org/jmlr/2016/chen2016jmlr-statisticalcomputational/)BibTeX
@article{chen2016jmlr-statisticalcomputational,
title = {{Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices}},
author = {Chen, Yudong and Xu, Jiaming},
journal = {Journal of Machine Learning Research},
year = {2016},
pages = {1-57},
volume = {17},
url = {https://mlanthology.org/jmlr/2016/chen2016jmlr-statisticalcomputational/}
}