# The Effects of Randomness on the Stability of Node Embeddings

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

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

- [Similarity of Neural Network Models: A Survey of Functional and Representational Measures](https://mlsanity.com/paper/2305.06329/) (2023)
- [Cleora: A Simple, Strong and Scalable Graph Embedding Scheme](https://mlsanity.com/paper/2102.02302/) (2021)
- [Structack: Structure-based Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2107.11327/) (2021)
- [On the Prediction Instability of Graph Neural Networks](https://mlsanity.com/paper/2205.10070/) (2022)
- [Towards Measuring Representational Similarity of Large Language Models](https://mlsanity.com/paper/2312.02730/) (2023)
- [Topological Node2vec: Enhanced Graph Embedding via Persistent Homology](https://mlsanity.com/paper/2309.08241/) (2023)
- [On the Surprising Behaviour of node2vec](https://mlsanity.com/paper/2206.08252/) (2022)
- [Geometric instability of graph neural networks on large graphs](https://mlsanity.com/paper/2308.10099/) (2023)
- [CAFIN: Centrality Aware Fairness inducing IN-processing for Unsupervised Representation Learning on Graphs](https://mlsanity.com/paper/2304.04391/) (2023)
- [Link Prediction or Perdition: the Seeds of Instability in Knowledge Graph Embeddings](https://mlsanity.com/paper/2606.03365/) (2026)
- [Distilling Influences to Mitigate Prediction Churn in Graph Neural Networks](https://mlsanity.com/paper/2310.00946/) (2023)
- [Normalized Space Alignment: A Versatile Metric for Representation Analysis](https://mlsanity.com/paper/2411.04512/) (2024)
- [The Impact of Dimensionality on the Stability of Node Embeddings](https://mlsanity.com/paper/2604.08492/) (2026)
- [TopoAlign: Topology-Aware Visual Representation Alignment](https://mlsanity.com/paper/2605.25541/) (2026)
- [Historical Anchors for Scientific Forecasting on Human-Aware Knowledge Graphs](https://mlsanity.com/paper/2610.14023/) (2026)

## Abstract (arXiv)

We systematically evaluate the (in-)stability of state-of-the-art node embedding algorithms due to randomness, i.e., the random variation of their outcomes given identical algorithms and graphs. We apply five node embeddings algorithms---HOPE, LINE, node2vec, SDNE, and GraphSAGE---to synthetic and empirical graphs and assess their stability under randomness with respect to (i) the geometry of embedding spaces as well as (ii) their performance in downstream tasks. We find significant instabilities in the geometry of embedding spaces independent of the centrality of a node. In the evaluation of downstream tasks, we find that the accuracy of node classification seems to be unaffected by random seeding while the actual classification of nodes can vary significantly. This suggests that instability effects need to be taken into account when working with node embeddings. Our work is relevant for researchers and engineers interested in the effectiveness, reliability, and reproducibility of node embedding approaches.