Local Statistics, Semidefinite Programming, and Community Detection II
summary
Degree-2 local statistics SDP with constraints given by the l-length non-backtracking power of the centered adjacency matrix certifies that the null Erdős–Rényi model has inner product at most square-root(d)^l (up to 1+ε factors) so it separates null from planted above the Kesten–Stigum threshold. Proof deletes a tiny set of bad vertices (short cycles or high-degree neighborhoods), bounds the operator norm via kth moment trace, encodes contributing closed walks on a spanning tree plus few excess edges, uses LP/combinatorial bounds, and yields a polynomial-time, adversarially robust distinguisher; recovery and tight lower bounds remain open.
AI-written summary · about
chapters (8)
- 0:00Problem introduction
- 3:27Spectral bounds and M
- 6:26Bounding the kth moment
- 9:58Combinatorics of walks
- 12:05Tree-based encoding
- 16:34Handling cycles
- 21:01Future research directions
- 25:00Q&A session
related talks
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)
39mLocal Algorithms for Community Detection
45mCommunity Detection with the Non-Backtracking Operator
01h 02mDuality 2
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
43mGlobal Community Detection Using Individual-Centered Partial Information Networks