# Asymptotics of Network Embeddings Learned via Subsampling

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 76 references that are in the map.
- First posted on arXiv 6 Jul 2021.

## Builds on (most cited first, 14 of 14)

- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Using Embeddings to Correct for Unobserved Confounding in Networks](https://mlsanity.com/paper/1902.04114/) (2019)
- [Minimum-Distortion Embedding](https://mlsanity.com/paper/2103.02559/) (2021)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Graph Neural Networks Exponentially Lose Expressive Power for Node Classification](https://mlsanity.com/paper/1905.10947/) (2019)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data](https://mlsanity.com/paper/1806.10701/) (2018)
- [Exact Recovery of Community Structures Using DeepWalk and Node2vec](https://mlsanity.com/paper/2101.07354/) (2021)

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

- [Using Embeddings for Causal Estimation of Peer Influence in Social Networks](https://mlsanity.com/paper/2205.08033/) (2022)
- [Accurately Modeling Biased Random Walks on Weighted Graphs Using textitNode2vec+](https://mlsanity.com/paper/2109.08031/) (2021)
- [Statistical Guarantees for Link Prediction using Graph Neural Networks](https://mlsanity.com/paper/2402.02692/) (2024)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks](https://mlsanity.com/paper/2505.14867/) (2025)
- [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)
- [Estimation of embedding vectors in high dimensions](https://mlsanity.com/paper/2312.07802/) (2023)
- [Bypassing Skip-Gram Negative Sampling: Dimension Regularization as a More Efficient Alternative for Graph Embeddings](https://mlsanity.com/paper/2405.00172/) (2024)
- [Information Loss and Disparate Effects in Network Embeddings](https://mlsanity.com/paper/2509.12396/) (2025)

## Abstract (arXiv)

Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency.