Learning Probabilistic Models for Graph Partitioning in the Presence of Noise

on YouTube ↗47m

" summary

Semidefinite relaxations plus a simple greedy clustering on the SDP vectors give provable guarantees: a constant‑factor approximation for minimum balanced cut when inter‑cluster edges are permutation‑invariant, and partial community recovery even if up to ε m corruptions occur or the data is within O(ε m) KL‑divergence of an SBM. Results require polylogarithmic average degree (roughly log^2 n) and show most SDP edge lengths concentrate so the method recovers communities up to O(ε) error.

AI-written summary · about

" chapters (29)

1. 0:00Intro
2. 0:52Graph Partitioning problems
3. 3:10Average-case Analysis
4. 4:11Models for Clustering Graphs
5. 5:03Goal 1: Approximating Objective
6. 6:21Goal 2: Learning Probabilistic model
7. 8:06A simple random model : SBM
8. 11:02Prior Work on Learning SBMS
9. 12:13Learning SBMs Exactly
10. 14:16Sparse Regime
11. 18:56How Robust are Usual Approaches?
12. 20:09Drawbacks of Random Models
13. 20:54Beyond Simple Random models
14. 21:39Monotone Adversaries Feige-Kilian
15. 25:25Semi-random model in Makarychev.Makarychev V'12
16. 26:45Recovering the planted Partition
17. 28:30Random Permutation Invariant Edges (PIE) model [Makarychev-Makarychev-V'14]
18. 30:05Advantages of Model
19. 31:05Result: Constant factor approximation algorithms in PIE model
20. 35:05Learning with Modeling Errors
21. 36:23Model Misspecification in KL divergence
22. 37:31Robustness Learning Guarantees
23. 40:07Related Work
24. 40:49Algorithm Overview: Relax and Cluster
25. 41:23SDP Relaxations
26. 42:04Intracluster & Intercluster Distances
27. 42:23Geometrical Clustering of SDP
28. 42:44The Algorithm
29. 43:23Distance concentration

" 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)
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 51mExact Recovery via Convex RelaxationsMoses Charikar · Spectral Algorithms: From Theory to Practice 2014
• 47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)Fedrico Ricci-Tersenghi · Random Instances and Phase Transitions (Simons Institute, 2016)
• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making