"Community Detection with a Subsampled Semidefinite Program"Abdalla Teixeira, PedroSemidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. In the context of community detection in the stochastic block model, in which the goal is to recover planted communities in a graph, semidefinite programs can achieve optimal performance according to the information theoretic threshold and they are also robust against monotone adversarial contamination. However, semidefinite programs are slow in practice, so speed up techniques such as sketching are often considered. Mixon and Xie considered the community detection problem with two balanced communities, they proposed a sketching framework in which a semidefinite program is solved only on a sampled subgraph of the network. The computational savings comes from solving the semidefinite program in a considerably smaller graph. They conjectured a certain threshold for the technique to work. In this talk, we present a proof for the conjecture of Mixon and Xie. (This is a joint work with Afonso S. Bandeira) |
| http://univie.ac.at/projektservice-mathematik/e/talks/Abdalla Teixeira_2021-06_SBM_Scketching_Paper-ICCHApdf.pdf |
« back