A Semidefinite Program for Structured Blockmodels
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored to other instances of the blockmodel, such as non-assortative networks and overlapping communities. We establish label recovery in sparse settings, with conditions that are analogous to recent results for community detection. In settings where the data is not generated by a blockmodel, we give an oracle inequality that bounds excess risk relative to the best blockmodel approximation. Simulations are presented for community detection, for overlapping communities, and for latent space models.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming with diagonal constraints. The approach, which we call the Mixing method, is extremely simple to implement, has no f…
Learning Word EmbeddingsWord EmbeddingsStructured Semidefinite Programming for Recovering Structured Preconditioners
We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving…
Sketching semidefinite programs for faster clustering
Many clustering problems enjoy solutions by semidefinite programming. Theoretical results in this vein frequently consider data with a planted clustering and a notion of signal strength such that the semidefinite program…
ClusteringGraph ClusteringLearning Semidefinite Regularizers
Regularization techniques are widely employed in optimization-based approaches for solving ill-posed inverse problems in data analysis and scientific computing. These methods are based on augmenting the objective with a …
Dictionary LearningCommunity Detection with a Subsampled Semidefinite Program
Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so …
ClusteringCommunity DetectionStochastic Block Model