Carey E. Priebe
Johns Hopkins University
Baltimore, Maryland, USA

Title: Adjacency Spectral Graph Embedding & Subsequent Inference

Escuela de Estadistica
Universidad de Costa Rica
June 02-03-04, 2014

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;
this result is strengthened in Lyzinski et al. (2013, submitted).
For the more general random dot product graph model, an example of a latent position model, 
Sussman et al. (2014, 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) provides distributional results, akin to a central limit theorem, 
for the residuals between the estimated and true latent positions,
which allows the potential for deeper understanding of these methods;
this result is employed in an empirical Bayes setting in Suwan et al. (2014, submitted).
Tang et al. (2014, submitted) extends the scope of our work to the problem of
testing hypotheses on a pair of random dot product graphs on the same vertex set.
In summary, this body of 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. 

http://arxiv.org/abs/1108.2228
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.

http://arxiv.org/abs/1205.0309
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.

http://arxiv.org/abs/1310.0532
V. Lyzinski, D.L. Sussman, M. Tang, A. Athreya, and C.E. Priebe,
"Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding,"
submitted for publication, 2013.

http://arxiv.org/abs/1207.6745
D.L. Sussman, M. Tang, and C.E. Priebe,
"Consistent latent position estimation and vertex classification for random dot product graphs,"
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 36, No. 1, pp. 48-57, 2014.

http://arxiv.org/abs/1212.1182
M. Tang, D.L. Sussman, and C.E. Priebe,
"Universally consistent vertex classification for latent positions graphs,"
Annals of Statistics, Vol. 41, No. 3, pp. 1406-1430, 2013.

http://arxiv.org/abs/1305.4893
M. Tang, Y. Park, and C.E. Priebe,
"Out-of-sample extension for latent position graphs,"
submitted for publication, 2013.

http://arxiv.org/abs/1305.7388
A. Athreya, V. Lyzinski, D.J. Marchette, C.E. Priebe, D.L. Sussman, and M. Tang,
"A limit theorem for scaled eigenvectors of random dot product graphs,"
submitted for publication, 2013.

http://arxiv.org/abs/1405.6070
S. Suwan, D.S. Lee, R. Tang, D.L. Sussman, M. Tang, and C.E. Priebe,
"Empirical Bayes Estimation for the Stochastic Blockmodel,"
submitted for publication, 2014.

http://arxiv.org/abs/1403.7249
M. Tang, A. Athreya, D.L. Sussman, V. Lyzinski, and C.E. Priebe,
"Two-sample Hypothesis Testing for Random Dot Product Graphs via Adjacency Spectral Embedding,"
submitted for publication, 2014.