Lecture Notes on Spectral Graph Methods

Aug 17, 2016 - 8.4.3 How large can the spectral gap be? ...... to a point cloud (which is an extension of the graph Laplacian from the empirical data points to.
2MB Sizes 11 Downloads 766 Views
Lecture Notes on Spectral Graph Methods

arXiv:1608.04845v1 [cs.DS] 17 Aug 2016

Michael W. Mahoney∗

∗ International Computer Science Institute and Department of Statistics, University of California at Berkeley, Berkeley, CA. E-mail: [email protected]

Abstract These are lecture notes that are based on the lectures from a class I taught on the topic of Spectral Graph Methods at UC Berkeley during the Spring 2015 semester. Spectral graph techniques are remarkably broad, they are widely-applicable and often very useful, and they also come with a rich underlying theory, some of which provides a very good guide to practice. Spectral graph theory is often described as the area that studies properties of graphs by studying properties of eigenvalues and eigenvectors of matrices associated with the graph. While that is true, especially of “classical” spectral graph theory, many of the most interesting recent developments in the area go well beyond that and instead involve earlystopped (as well as asymptotic) random walks and diffusions, metric embeddings, optimization and relaxations, local and locally-biased algorithms, statistical and inferential considerations, etc. Indeed, one of the things that makes spectral graph methods so interesting and challenging is that researchers from different areas, e.g., computer scientists, statisticians, machine learners, and applied mathematicians (not to mention people who actually use these techniques), all come to the topic from very different perspectives. This leads them to parameterize problems quite differently, to formulate basic problems as well as variants and extensions of basic problems in very different ways, and to think that very different things are “obvious” or “natural” or “trivial.” These lectures will provide an overview of the theory of spectral graph methods, including many of the more recent developments in the area, with an emphasis on some of these complementary perspectives, and with an emphasis on those methods that are useful in practice. I have drawn liberally from the lectures, notes, and papers of others, often without detailed attribution in each lecture. Here are the sources upon which I drew most heavily, in rough order of appearance over the semester. • “Lecture notes,” from Spielman’s Spectral Graph Theory class, Fall 2009 and 2012 • “Survey: Graph clustering,” in Computer Science Review, by Schaeffer • “Geometry, Flows, and Graph-Partitioning Algorithms,” in CACM, by Arora, Rao, and Vazirani • “Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory,” by Trevisan • “Expander graphs and their applications,” in Bull. Amer. Math. Soc., by Hoory, Linial, and Wigderson • “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” in JACM, by Leighton and Rao • “Efficient Maximum Flow Algorithms,” in CACM, by Goldberg and Tarjan • “A Tutorial on Spectral Clustering,” in Statistics and Computing, by von Luxburg • “A kernel view of the dimensionality reduction of manifolds,” in ICML, by Ham, et al. • “Laplacian Eigenmaps for dimensionality reduction and data representation,” in Neural Computation, by Belkin and Niyogi • “Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization,” in IEEE-PAMI, by Lafon and Lee • “Transductive learning via spectral graph partitioning,” in ICML, by Joachims • “Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions,” in ICML, by Zhu, Ghahramani, and Lafferty • “Learning with local and global consistency,” in NIPS, by Zhou et al. • “Random Walks and Electric Networks,” in arXiv, by Doyle and Snell • “Implementing regularization implicitly via approximate eigenvector computation,” in ICML, by Mahoney and Orecchia • “Regularized Laplacian Estimation and Fast Eigenvector Approximation,” in NIPS, by Perry and Mahoney • “Spectral Ranking”, in arXiv, by Vigna • “PageRank beyond the Web,” in SIAM Review, by Gleich • “The Push Algorithm for Spec