In this talk, I will discuss a novel relaxation approach for the graph clustering problem. In particular, I will provide conditions on the underlying graph which guarantee that the solution of this relaxation recovers the desired community structure. Subsequently, I will focus on algorithmic approaches for solving this semidefinite program based on the alternating direction method of multipliers and low-rank factorization, and discuss the challenges associated with applying these methods to large-scale networks.