  We consider the problem of identifying the densest k-node subgraph in a given
graph. We write this problem as an instance of rank-constrained cardinality
minimization and then relax using the nuclear and 11 norms. Although the
original combinatorial problem is NP-hard, we show that the densest k-subgraph
can be recovered from the solution of our convex relaxation for certain program
inputs. In particular, we establish exact recovery in the case that the input
graph contains a single planted clique plus noise in the form of corrupted
adjacency relationships. We consider two constructions for this noise. In the
first, noise is introduced by an adversary deterministically deleting edges
within the planted clique and placing diversionary edges. In the second, these
edge corruptions are performed at random. Analogous recovery guarantees for
identifying the densest subgraph of fixed size in a bipartite graph are also
established, and results of numerical simulations for randomly generated graphs
are included to demonstrate the efficacy of our algorithm.
