Finding dense sub-structures in big graphs is a central problem in data analytics. In this work, we develop a novel algorithmic framework for the densest k-subgraph problem. Our algorithm finds provably good solutions by exploring a low-dimensional subspace of the data. We provide a-priori performance guarantees that depend on the spectrum of the graph. We use these bounds to establish constant factor approximations, under various spectral assumptions.

A major advantage is that our algorithm runs in nearly linear time when the graph satisfies mild conditions. Moreover, our framework is scalable and parallelizable. We illustrate this by implementing it in MapReduce using more than 800 cores on Amazon EC2. This enables us to find dense subgraphs on massive graphs having billions of edges.