Generalized Cheeger Inequalities and Constrained Clustering

on YouTube ↗49m

" summary

Presents generalized Cheeger inequalities relating graph spectral properties to cluster conductance and uses those inequalities to develop constrained clustering algorithms; focuses on spectral methods (eigenvalues/eigenvectors of graph Laplacians) and shows how these bounds guide clustering under constraints.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 4:53The sparsest cut problem
3. 7:25The Graph Laplacian
4. 8:57Spectral Relaxation
5. 12:19Eigen-Solvers in Practice
6. 12:46Spectral vs Combinatorial Algorithms for cut problems
7. 20:26is Cheeger inequality tight?
8. 21:01is Cheeger method better than inequality?
9. 24:31Reasons for optimism
10. 27:24Fixing the path
11. 33:01Theoretical intuition so far
12. 35:16Constrained Clustering
13. 38:15Algorithm for generalized k-way partitioning
14. 40:03Summarizing the results
15. 43:04Some results
16. 44:08Open questions

" related talks

• 45mOn the Estimation of the Cheeger ConstantEry Arias-Castro · Spectral Algorithms: From Theory to Practice 2014
• 40mThe Hidden Convexity of Spectral ClusteringLuis Rademacher · Spectral Algorithms: From Theory to Practice 2014
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 01h 05mLog-concave Polynomials and Spectral Independence 1Kuikui Liu · Analysis and TCS Boot Camp 2023
• 26mMathematical Approaches to ClusteringJoseph Ross · MLconf Online 2020
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 25mConstrained Rank Aggregation and Correlation ClusteringOlgica Milenkovic · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 38mThe Impact of Regularization in Spectral ClusteringBin Yu · Spectral Algorithms: From Theory to Practice 2014