Community Detection with the Non-Backtracking Operator

on YouTube ↗45m

" summary

Shows that the non-backtracking operator (the edge-to-edge B matrix) produces an eigenvalue outside the bulk for sparse random graphs when the signal-to-noise ratio crosses the sharp detectability threshold (roughly when the relevant eigenvalue exceeds 1), gives a practical algorithm that computes the leading eigenvector on directed edges and projects it to vertices, and proves this outperforms adjacency-based spectral methods on stochastic block models; demonstrates performance on real data like the Karate-club dataset and handles extremely sparse regimes.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 6:31Directed and undirected graphs
3. 13:52Spectral properties and gap
4. 20:19Galton-Watson process and applications
5. 27:08Community detection with non-backtracking
6. 34:19Comparison with classical spectral methods
7. 40:56Stochastic models: limits and cases
8. 44:13Conclusion

" related talks

• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 43mGlobal Community Detection Using Individual-Centered Partial Information NetworksRachel Wang · Statistics in the Big Data Era 2022
• 29mApplying Randomized Methods for Zonotope Enumeration and...David Gleich · Randomized Numerical Linear Algebra and Applications 2018
• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 01h 02mGraph PoweringEmmanuel Abbe · Optimization, Statistics and Uncertainty