The Effects of Randomness on the Stability of Node Embeddings

Tobias Schumacher, Hinrikus Wolf, Martin Ritzert, Florian Lemmerich, Jan Bachmann, Florian Frantzen, Max Klabunde, Martin Grohe, Markus Strohmaier

TL;DR

Node embedding algorithms are a staple of modern graph analysis, but their reliance on randomness—from initialization to neighborhood sampling—creates a hidden reproducibility crisis. This paper reveals that while overall classification accuracy remains stable across different runs, the underlying geometry of the embedding spaces and the specific predictions for individual nodes can vary wildly, posing significant risks for high-stakes applications.

What Problem Does This Paper Address?

Node embedding techniques (like node2vec or GraphSAGE) map nodes in a graph to vectors in a continuous, low-dimensional space. These vectors are then used for downstream tasks like node classification or link prediction. However, most of these algorithms are stochastic: they use random walks, random parameter initialization, or stochastic gradient descent.

The authors tackle a fundamental question: How stable are these embeddings? If you run the same algorithm on the exact same graph twice, do you get the same results? While researchers often report average performance, the "instability" of individual node representations is rarely discussed. This is crucial for reliability, especially when embeddings are used to make decisions about individuals in social networks or biological entities in protein-interaction maps.

Illustration of how randomness leads to different geometric and predictive outcomes despite using the same input graph.

Methods

The researchers systematically evaluated five state-of-the-art algorithms: HOPE, LINE, node2vec, SDNE, and GraphSAGE. They assessed stability through two lenses:

  1. Geometric Stability: They measured how much the relative positions of nodes changed. Because embedding spaces can be rotations of one another, they used Aligned Cosine Similarity (using Procrustes alignment to "fix" rotations) and k-NN Jaccard Similarity (checking if a node’s nearest neighbors remained the same).
  2. Downstream Stability: They trained classifiers (like Random Forests and AdaBoost) on these embeddings to see if the final predictions changed. They introduced the concept of a "stable core"—the percentage of nodes that receive the same classification label across multiple runs.

Datasets

The study utilized a mix of synthetic and empirical datasets:

  • Synthetic: Barabasi-Albert (scale-free) and Watts-Strogatz (small-world) graphs, allowing the authors to control for size and density.
  • Empirical: Five diverse real-world networks:
  • BlogCatalog (social network)
    • Cora (citation network)
    • Facebook (government site likes)
    • Protein (biological interactions)
    • Wikipedia (word co-occurrence)

Key Insights and Ideas

  • The Accuracy Illusion: One of the most striking findings is that overall classification accuracy (Micro-F1) is remarkably robust to randomness. However, this masks a deeper instability: the specific nodes that are misclassified change from run to run.
  • The Volatility Spectrum: Algorithms vary significantly in their stability. HOPE, which is based on SVD factorization, is nearly deterministic. Conversely, GraphSAGE is highly volatile due to its neighborhood sampling approach.
  • The Centrality Paradox: Intuitively, one might expect "central" nodes (those with many connections) to be more stable because they are visited more often by random walks. The study found this isn't necessarily true; for most algorithms, a node's position in the graph does not guarantee a stable embedding.
  • Local vs. Global Stability: The authors found that while a node's exact nearest neighbors might change (low Jaccard similarity), the general "cluster" it belongs to remains somewhat consistent (high second-order cosine similarity).

Key Results

  • Geometric Instability: For algorithms like LINE, node2vec, and SDNE, the aligned cosine similarity typically fell between 0.8 and 0.9. While this sounds high, it corresponds to angular differences of over 20 degrees between runs.
  • The Jaccard Gap: In many cases, only 20% to 80% of a node's nearest neighbors remained the same across different runs. For GraphSAGE, the Jaccard similarity was often near zero.
  • Prediction Flips: The "stable core" results were sobering. For the AdaBoost classifier, the stable core was often below 5% for several algorithms. This means that for 95% of the nodes, the predicted label could flip simply by changing the random seed of the embedding algorithm.
Comparison of geometric stability across different datasets and algorithms.

Limitations and Future Work

The authors acknowledge that their study is limited to small and medium-sized graphs due to the computational cost of running 30+ embeddings per dataset. They also note that stability might be influenced by specific implementation details of the libraries used.

Future Directions: * Theoretical Analysis: Moving beyond empirical observation to identify the mathematical sources of instability within the algorithms. * Stability as a Feature: Interestingly, the authors suggest that instability could be a "feature" for privacy—making it harder to recover sensitive information about deleted nodes. * Robust Algorithm Design: Developing new embedding methods that explicitly control for variability to ensure reproducible science and reliable engineering.

Summary updated

Abstract

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.
BibTeX
@inproceedings{schumacher2021effects,
  author = {Tobias Schumacher and Hinrikus Wolf and Martin Ritzert and Florian Lemmerich and Jan Bachmann and Florian Frantzen and Max Klabunde and Martin Grohe and Markus Strohmaier},
  title = {{The Effects of Randomness on the Stability of Node Embeddings}},
  booktitle = {PKDD/ECML Workshops},
  year = {2021},
  doi = {10.1007/978-3-030-93736-2\_16},
}
Figure