Local Statistics, Semidefinite Programming, and Community Detection
summary
Proposes a concrete local statistics SDP hierarchy that adds affine constraints built from centered non-backtracking walk constraints (weighted counts) to a PSD, unit-diagonal relaxation; proves these constraints let the SDP detect the stochastic block model versus Erdős–Rényi down toward the conjectured Kesten–Stigum threshold d lambda^2 = 1 as the walk length l grows constant, and in the regular graph case shows a degree‑2/local‑degree constant instance SDP succeeds above the KS threshold and fails below it.
AI-written summary · about
chapters (8)
- 0:00Introduction and workshop theme
- 1:02Inference and planted models
- 5:30Community detection problem
- 8:07SDP approaches to detection
- 13:51Refining SDP with constraints
- 20:20General local statistics framework
- 27:36Results and future outlook
- 30:27Q&A and concluding remarks
related talks
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
01h 02mDuality 2
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
44mCombinatorial Characterizations in Semidefinite Programming Duality: ...
46mFaster SDP Hierarchy Solvers for Local Rounding Algorithms
25mLucky Talk: From Coding to Clustering