# Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings

arXiv: https://arxiv.org/abs/1910.00423 · HTML: https://mlsanity.com/paper/1910.00423/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2019.

## Built on by (most cited first, 5 of 5)

- [Asymptotics of ℓ2 Regularized Network Embeddings](https://mlsanity.com/paper/2201.01689/) (2022)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [Bias-Corrected Joint Spectral Embedding for Multilayer Networks with Invariant Subspace: Entrywise Eigenvector Perturbation and Inference](https://mlsanity.com/paper/2406.07849/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)

## Abstract (arXiv)

Graph embeddings, a class of dimensionality reduction techniques designed for relational data, have proven useful in exploring and modeling network structure. Most dimensionality reduction methods allow out-of-sample extensions, by which an embedding can be applied to observations not present in the training set. Applied to graphs, the out-of-sample extension problem concerns how to compute the embedding of a vertex that is added to the graph after an embedding has already been computed. In this paper, we consider the out-of-sample extension problem for two graph embedding procedures: the adjacency spectral embedding and the Laplacian spectral embedding. In both cases, we prove that when the underlying graph is generated according to a latent space model called the random dot product graph, which includes the popular stochastic block model as a special case, an out-of-sample extension based on a least-squares objective obeys a central limit theorem about the true latent position of the out-of-sample vertex. In addition, we prove a concentration inequality for the out-of-sample extension of the adjacency spectral embedding based on a maximum-likelihood objective. Our results also yield a convenient framework in which to analyze trade-offs between estimation accuracy and computational expense, which we explore briefly.