Correlated Stochastic Block Models: Graph Matching And Community Recovery

on YouTube ↗45m

" summary

Model uses P = A log N / N and Q = B log N / N and generates two subsampled, permuted copies; exact graph matching is feasible down to the information-theoretic threshold S^2(A + B)/2 > 1. The natural max-edge-agreement estimator (quadratic assignment maximizing agreeing edges) recovers the latent permutation with high probability when that condition holds; equivalently the correctly matched intersection graph is connected. Using that matching, unioning the graphs gives exact community recovery beyond the single-graph threshold; the estimator is not known to be polynomial-time.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:00Community Recovery
3. 1:39Stochastic Block Model
4. 4:17Correlated Networks
5. 6:22Correlated Stochastic Block Model
6. 10:15Exact Recovery
7. 15:37Results
8. 24:44Graph Matching
9. 34:38Open Problem
10. 40:38Questions

" related talks

• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 24mStochastic Block Models with R: Statistically rigorous clusteringNick Strayer · rstudio::conf 2019
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 54mNode Privacy, High-dimensional Graph Summaries, and Block ModelsAdam M. Smith · Privacy and the Science of Data Analysis 2019