Title: Semidefinite relaxation of the clustering problem and first-order methods for their solution

Abstract: I will discuss a novel relaxation approach for the graph clustering problem. Although intractable in worst-case, much recent research has established that clusters can be recovered if the underlying network or data is well-behaved. 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.