  Given an undirected graph, the Densest-k-Subgraph problem (DkS) seeks to find
a subset of k vertices such that the sum of the edge weights in the
corresponding subgraph is maximized. The problem is known to be NP-hard, and is
also very difficult to approximate, in the worst-case. In this paper, we
present a new convex relaxation for the problem. Our key idea is to reformulate
DkS as minimizing a submodular function subject to a cardinality constraint.
Exploiting the fact that submodular functions possess a convex, continuous
extension (known as the Lov\'asz extension), we propose to minimize the
Lov\'asz extension over the convex hull of the cardinality constraints.
Although the Lov\'asz extension of a submodular function does not admit an
analytical form in general, for DkS we show that it does. We leverage this
result to develop a highly scalable algorithm based on the Alternating
Direction Method of Multipliers (ADMM) for solving the relaxed problem. Coupled
with a pair of fortuitously simple rounding schemes, we demonstrate that our
approach outperforms existing baselines on real-world graphs and can yield high
quality sub-optimal solutions which typically are a posteriori no worse than
65-80\% of the optimal density.
