Graph clustering and community detection via Semidefinite Programming
Semidefinite Programming (SDP): Let denote the adjacency matrix of , and the ‘all ones’ vector. We then use the following SDP: Here denotes the usual scalar product between matrices, and we write if is positive semidefinite. Solving this SDP by generic methods can be quite slow. We reduce the complexity by constraining to have rank , and changing variables. We introduce the ‘spin’ variables and attempt to solve the following non-convex problem: where . Somewhat surprisingly, we found that as small as to is sufficient to guarantee global convergence in most practical examples (even if ). The embedding is simply a low-dimensional projection of the spin (with ). PaperA. Javanmard, A. Montanari, and F. Ricci-Tersenghi, Phase Transitions in Semidefinite Relaxations, 2015 PeopleRelated PapersS. Burer, R. D.C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming 2003 A. Montanari and S.Sen, Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection, 201 |