Community detection with a subsampled semidefinite program

DOI10.1007/S43670-022-00023-9MaRDI QIDQ2143169zbMATH OpenOpenAlexFDO

Authors Pedro Abdalla, Afonso S. Bandeira

Publication date 31 May 2022

Published in Sampling Theory, Signal Processing, and Data Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.01419

zbMATH Keywords

community detectionsemidefinite programmingclustering algorithmsgraph and network theory

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Semidefinite programming (90C22) Detection theory in information and communication theory (94A13)

Abstract: 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 speed up techniques such as sketching are often considered. In the context of community detection in the stochastic block model, Mixon and Xie cite{mixon2020sketching} have recently proposed a sketching framework in which a semidefinite program is solved only on a subsampled subgraph of the network, giving rise to significant computational savings. In this short paper, we provide a positive answer to a conjecture of Mixon and Xie about the statistical limits of this technique for the stochastic block model with two balanced communities.

Recommendations

• Semidefinite programs on sparse random graphs and their application to community detection
• On semidefinite relaxations for the block model
• Community detection in sparse networks via Grothendieck's inequality
• Phase transitions in semidefinite relaxations
• Subsampling algorithms for semidefinite programming

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2038320 (Why is no real title available?)
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Community detection and stochastic block models: recent developments
• Dimensionality reduction of SDPs through sketching
• Exact Recovery in the Stochastic Block Model
• High-dimensional probability. An introduction with applications in data science
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Random Laplacian matrices and convex relaxations
• Sketching Semidefinite Programs for Faster Clustering
• Sketching as a tool for numerical linear algebra

Cited in

(4)

• Optimization via low-rank approximation for community detection in networks
• On semidefinite relaxations for the block model
• Semidefinite programs on sparse random graphs and their application to community detection
• Community detection in sparse networks via Grothendieck's inequality

This page was built for publication: Community detection with a subsampled semidefinite program

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143169)