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.
Methods
The researchers systematically evaluated five state-of-the-art algorithms: HOPE, LINE, node2vec, SDNE, and GraphSAGE. They assessed stability through two lenses:
- 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).
- 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.
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