Graph clustering and community detection via Semidefinite Programming
|
Motivation: Given an undirected graph , we want to partition its vertices into
disjoint subsets. This task arises in applications to clustering, and network analysis.
A common strategy is the following:
Construct a low-dimensional embedding of the vertices. Explicitly, for each vertex ,
contruct a vector , with ambient dimension .
Use some greedy procedure to cluster the points .
The code presented here provides an efficent way to implement step 1 by
solving a semidefinite programming relaxation.
On the left side, we show a small two-dimensional example. (A two-dimensional embedding of
a network of political books from Mark Newman's repository. Colors correspond to political
orientation. The embedding separates quite clearly two groups.)
|
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 ).
Paper
A. Javanmard, A. Montanari, and F. Ricci-Tersenghi, Phase Transitions in Semidefinite Relaxations, 2015
People
Related Papers
S. 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
|