Carey E. Priebe has been named a 2013
University of Canterbury, Christchurch, New Zealand.
Professor Priebe will teach & lecture in New Zealand during summer 2013.
John (Jack) Angus Erskine
Carey E. Priebe
2013 Erskine Fellow
2009 Erskine Fellow
August 02, 2013
University of Canterbury, Christchurch, New Zealand
Title: Adjacency-Spectral Graph Embedding
Abstract: 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. For the stochastic blockmodel, with a finite number of blocks of stochastically equivalent vertices, Sussman et al. (2012, JASA) and Fishkind et al. (2013, SIMAX) show that clustering the embedded points using k-means accurately partitions the vertices into the correct blocks, even when the embedding dimension is misspecified or the number of blocks is unknown. For the more general random dot product graph model, an example of a latent position model, Sussman et al. (2013, PAMI) shows that the latent positions are consistently estimated by the embedding which then allows for accurate learning in a supervised vertex classification framework. Tang et al. (2013, AoS) and Tang et al. (2013, submitted) strengthen these results to more general latent position models and for an efficient embedding of vertices which were not observed in the original graph. Athreya et al. (2013, submitted) provide distributional results, akin to a central limit theorem, for the residuals between the estimated and true latent positions which provides the potential for deeper understanding of these methods. In summary, this work demonstrates that for a broad class of graph models and inference tasks, adjacency-spectral embedding allows for accurate graph inference via standard multivariate methodology.
D.L. Sussman, M. Tang, D.E. Fishkind, and C.E. Priebe,
"A consistent adjacency spectral embedding for stochastic blockmodel graphs,"
Journal of the American Statistical Association, Vol. 107, No. 499, pp. 1119-1128, 2012.
D.E. Fishkind, D.L. Sussman, M. Tang, J.T. Vogelstein, and C.E. Priebe,
"Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown ,"
SIAM Journal on Matrix Analysis and Applications, Vol. 34, No. 1, pp. 23-39, 2013.
D.L. Sussman, M. Tang, C.E. Priebe,
"Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs,"
IEEE Transactions on Pattern Analysis and Machine Intelligence, accepted for publication, 2013.
M. Tang, D.L. Sussman, and C.E. Priebe,
"Universally consistent vertex classification for latent positions graphs,"
Annals of Statistics, accepted for publication, 2013.
Minh Tang, Youngser Park, and Carey E. Priebe,
"Out-of-sample Extension for Latent Position Graphs,"
submitted for publication, 2013.
Avanti Athreya, Vince Lyzinski, David J. Marchette, Carey E. Priebe, Daniel L. Sussman, and Minh Tang,
"A limit theorem for scaled eigenvectors of random dot product graphs,"
submitted for publication, 2013.