Graph Clustering Algorithms (September 28, 2017)

Tselil Schramm (Simons Institute, UC Berkeley) One of the greatest advantages of representing data with graphs is access to generic algorithms for analytic tasks, such as clustering. In this talk I will describe some popular graph clustering algorithms, and explain why they are well-motivated from a theoretical perspective. ------------------- References from the Whiteboard: Ng, Andrew Y., Michael I. Jordan, and Yair Weiss. "On spectral clustering: Analysis and an algorithm." Advances in neural information processing systems. 2002. Lee, James R., Shayan Oveis Gharan, and Luca Trevisan. "Multiway spectral partitioning and higher-order cheeger inequalities." Journal of the ACM (JACM) 61.6 (2014): 37. ------------------- Additional Resources: In my explanation of the spectral embedding I roughly follow the exposition from the lectures of Dan Spielman (http://www.cs.yale.edu/homes/spielman..., focusing on the content in lecture 2. Lecture 1 also contains some additional striking examples of graphs and their spectral embeddings. I also make some imprecise statements about the relationship between the spectral embedding and the minimum-energy configurations of a mass-spring system. The connection is discussed more precisely here (https://www.simonsfoundation.org/2012.... License: CC BY-NC-SA 4.0 https://creativecommons.org/licenses/...