Limit theorems for eigenvectors of the normalized Laplacian for random graphs

Statistical inference on graphs is a burgeoning field of research in machine learning and statistics, with numerous applications to social network, neuroscience, etc. Many statistical inference procedures for graphs involve a preprocessing step of finding a representation of the vertices as points in some low-dimensional Euclidean space. This representation is usually given by the truncated eigendecomposition of the adjacency matrix or related matrices such as the combinatorial Laplacian or the normalized Laplacian. For example, given a point cloud lying in some purported low-dimensional manifold in a high-dimensional ambient space, many manifold learning or nonlinear dimension reduction algorithms such as Laplacian eigenmaps [5] and diffusion maps [15] use the eigenvectors of the normalized Laplacian constructed from a neighborhood graph of the points as a low-dimensional Euclidean representation of the point cloud before performing inference such as clustering or classification. Spectral clustering 1 algorithms such as the normalized cuts algorithm [35] proceed by embedding a graph into a low-dimensional Euclidean space followed by running K-means on the embedding to obtain a partitioning of the vertices.