Adjacency Spectral Embedding for Random Graphs

Job Candidate Talk
Friday, January 15, 2016 - 11:05am for 1 hour (actually 50 minutes)
Skiles 006
Daniel Sussman – Department of Statistics, Harward University
Vladimir Koltchinskii
The eigendecomposition of an adjacency matrix provides a way to embed a graph as points in finite dimensional Euclidean space. This embedding allows the full arsenal of statistical and machine learning methodology for multivariate Euclidean data to be deployed for graph inference. Our work analyzes this embedding, a graph version of principal component analysis, in the context of various random graph models with a focus on the impact for subsequent inference. We show that for a particular model this embedding yields a consistent estimate of its parameters and that these estimates can be used to accurately perform a variety of inference tasks including vertex clustering, vertex classification as well as estimation and hypothesis testing about the parameters.