Phase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)

on YouTube ↗47m

" summary

A semidefinite programming approach produces a fast, robust algorithm for community detection by optimizing a relaxed trace objective over low‑rank correlation matrices represented as m‑component vector updates, using coordinate‑wise ascent that aligns each vector to its local field and then projects via the principal direction. It tolerates tiny planted cliques that break spectral methods, runs on n≈10^5 in seconds on a laptop, achieves near‑Bayes performance within 2% of optimal, and needs only modest m (≈6–16, much less than √n).

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 0:25Outline of the talk
3. 1:14Communities detection problem
4. 1:59Benchmark for community detection
5. 2:37The hidden partition model
6. 3:41Assortative SBM with 2 equal-size groups
7. 5:18Maximum Likelihood (ML)
8. 6:10Lagrangian formulation
9. 6:56Spectral relaxation (PCA)
10. 8:02Spectral relaxation fails on sparse graphs
11. 8:35Why PCA fails?
12. 9:09Other spectral methods
13. 11:20Improved spectral methods fail on quasi-random graphs
14. 14:46SDP: a better relaxation?
15. 17:16SDP-based algorithm
16. 24:31The algorithm is very robust!
17. 25:06The algorithm is very fast!
18. 27:00SDP optimality
19. 27:36Different estimators
20. 28:34Statistical physics approach
21. 32:33Analytical solution: dense real case
22. 34:43Analytical solution: sparse case (SBM)
23. 36:35Approximate analytical solution (SBM)
24. 41:05Take-home messages

" related talks

• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 24mIs it easier to count communities than find them?Cynthia Rush, Fiona Skerman, Alexander S Wein, Dana Yang · ITCS 2023
• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro FactorizationPraneeth Netrapalli · Randomized Numerical Linear Algebra and Applications 2018
• 43mGlobal Community Detection Using Individual-Centered Partial Information NetworksRachel Wang · Statistics in the Big Data Era 2022