# Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming

arXiv: https://arxiv.org/abs/2601.03946 · HTML: https://mlsanity.com/paper/2601.03946/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 50 references that are in the map.
- First posted on arXiv 7 Jan 2026.

## Builds on (most cited first, 5 of 5)

- [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Convex optimization for the densest subgraph and densest submatrix problems](https://mlsanity.com/paper/1904.03272/) (2019)
- [A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering](https://mlsanity.com/paper/2403.11351/) (2024)
- [Harnessing the mathematics of matrix decomposition to solve planted and maximum clique problem](https://mlsanity.com/paper/2307.09022/) (2023)

## Abstract (arXiv)

We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries. This problem is a natural generalization of fundamental problems in combinatorial optimization, e.g., the densest subgraph, maximum clique, and maximum edge biclique problems, and has wide application the study of complex networks. Much recent research has focused on the development of sufficient conditions for exact solution of the densest submatrix problem via convex relaxation. The vast majority of these sufficient conditions establish identification of the densest submatrix within a graph containing exactly one large dense submatrix hidden by noise. The assumptions of these underlying models are not observed in real-world networks, where the data may correspond to a matrix containing many dense submatrices of varying sizes. We extend and generalize these results to the more realistic setting where the input matrix may contain many large dense subgraphs. Specifically, we establish sufficient conditions under which we can expect to solve the densest submatrix problem in polynomial time for random input matrices sampled from a generalization of the stochastic block model. Moreover, we also provide sufficient conditions for perfect recovery under a deterministic adversarial. Numerical experiments involving randomly generated problem instances and real-world collaboration and communication networks are used empirically to verify the theoretical phase-transitions to perfect recovery given by these sufficient conditions.