Bias-Adjusted Spectral Clustering In Multi-Layer Stochastic Block Models

on YouTube ↗38m

" summary

Proposes spectral clustering on the sum of squared adjacency matrices with diagonal removed to cancel a layerwise bias that grows like L, turning the problematic A^2 diagonal into a computable degree correction; proves error rate shrinks with more layers as fraction misclustered ≤ C sqrt(log)/(n rho sqrt(L)) under a multilayer SBM, with simulations (30 layers) showing clear gains in the moderate-sparsity regime. Applies to a real gene co-expression set of ~8,000 genes over 10 timepoints, K=8, and recovers temporally varying community activity.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 1:37Background
3. 2:22Example
4. 4:03Multilayer stochastic block model
5. 5:38Single layer community recovery
6. 6:44Layerwise positivity assumption
7. 9:36Least square approach
8. 10:49Least square approximation
9. 12:29Spectral clustering
10. 14:37Error decomposition
11. 18:27Simulation
12. 19:44Analysis
13. 27:49rnsteins Inequality
14. 29:58Hands and Writing Inequality
15. 30:33Gene Coexpression Network
16. 31:19Results
17. 34:40Temporal Analysis

" related talks

• 24mStochastic Block Models with R: Statistically rigorous clusteringNick Strayer · rstudio::conf 2019
• 38mThe Impact of Regularization in Spectral ClusteringBin Yu · Spectral Algorithms: From Theory to Practice 2014
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 49mSpectral Algorithms for Learning Latent Variable ModelsSham Kakade · Spectral Algorithms: From Theory to Practice 2014
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)