# Scalable Out-of-Sample Extension of Graph Embeddings Using Deep Neural Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2015.

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

- [Representation Learning via Manifold Flattening and Reconstruction](https://mlsanity.com/paper/2305.01777/) (2023)
- [When and How Does In-Distribution Label Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2405.18635/) (2024)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [High Performance Out-of-sample Embedding Techniques for Multidimensional Scaling](https://mlsanity.com/paper/2111.04067/) (2021)
- [Deep Diffusion Maps](https://mlsanity.com/paper/2505.06087/) (2025)

## Abstract (arXiv)

Several popular graph embedding techniques for representation learning and dimensionality reduction rely on performing computationally expensive eigendecompositions to derive a nonlinear transformation of the input data space. The resulting eigenvectors encode the embedding coordinates for the training samples only, and so the embedding of novel data samples requires further costly computation. In this paper, we present a method for the out-of-sample extension of graph embeddings using deep neural networks (DNN) to parametrically approximate these nonlinear maps. Compared with traditional nonparametric out-of-sample extension methods, we demonstrate that the DNNs can generalize with equal or better fidelity and require orders of magnitude less computation at test time. Moreover, we find that unsupervised pretraining of the DNNs improves optimization for larger network sizes, thus removing sensitivity to model selection.