How embedding dimension shapes the stability of network node representations

Node embedding algorithms, the workhorses of modern network analysis, are surprisingly fickle. Run the same method twice on the same graph with identical settings, and the resulting vector representations of nodes can differ substantially, along with the predictions built on top of them. A new large-scale study published in Applied Network Science now shows that one of the most basic design choices in these methods, the number of dimensions in the learned representation, plays a far more complicated role in this instability than researchers had assumed. The work systematically examined how embedding dimensionality affects stability across five widely used methods, and the answer, the authors report, depends strongly on both the algorithm and on how stability itself is defined.

The study was conducted by Tobias Schumacher, Simon Reichelt and Markus Strohmaier, who set out to close a gap in the graph representation learning literature. Previous work had established that repeated training runs of the same embedding algorithm can produce different representations and downstream predictions even when trained on the same data with identical hyperparameters. Dimensionality had occasionally appeared in those analyses as one factor among many, but it had never been examined systematically. In a regression analysis by earlier researchers, embedding dimension was included as a linear predictor and showed a statistically significant, moderately sized effect on stability, yet potential non-linear relationships remained unexplored. The new study addresses that gap with three objectives: characterizing how dimensionality affects stability, analyzing the relationship between stability and downstream performance across dimensions, and investigating how graph size and density modulate these effects.

The scale of the investigation is notable. The team analyzed five node embedding methods chosen to span a broad range of methodological approaches: ASNE, which jointly incorporates graph structure and node attributes; Deep Graph Infomax, known as DGI, which maximizes mutual information between local node representations and global graph summaries; GraphSAGE, a graph neural network that aggregates representations from sampled neighborhoods; node2vec, which learns representations from random walks using a skip-gram objective; and VERSE, which approximates graph-based node similarity measures with a shallow neural architecture. The researchers trained and analyzed more than 150,000 embeddings, spanning dimensions from 4 to 4096, seven empirical benchmark datasets covering citation, social, hyperlink and biological interaction networks, and synthetic Barabási-Albert and Watts-Strogatz graphs generated with controlled size and density.

Stability was assessed from two complementary perspectives. Representational stability measures how similar the embedding spaces themselves are across repeated runs, using measures such as aligned cosine similarity, k-nearest-neighbor Jaccard similarity, second-order cosine similarity and distance correlation. Functional stability, by contrast, concerns the consistency of downstream predictions obtained from those embeddings, quantified through measures including disagreement between hard class predictions, the stable core, and Jensen-Shannon divergence between predicted probability distributions. These two notions need not coincide: embeddings that differ substantially in representation space may nevertheless yield similar downstream predictions, and vice versa. For the empirical datasets, the authors generated 30 embeddings for each combination of method, dataset and dimensionality, and evaluated downstream performance through node classification and link prediction tasks using both a logistic regressor and a multilayer perceptron.

The headline finding is that dimensionality can substantially affect embedding stability, but no universal relationship emerged. Node2vec and ASNE generally became more stable at higher dimensions, with their neighborhood stability and hard-prediction stability often increasing toward high plateaus. GraphSAGE and VERSE, however, frequently exhibited non-monotonic behavior or decreasing stability. GraphSAGE showed a consistent pattern across local stability measures: stability increased toward a comparatively low peak at intermediate dimensions before declining again. VERSE’s similarity scores consistently decreased from initially high values at low dimensionality before partially recovering at higher dimensions. Global representational stability, measured across whole embedding spaces, displayed predominantly non-monotonic relationships with dimensionality for most methods, while local neighborhood stability more often increased with dimension.

Equally striking is what the study found about the relationship between stability and performance. Downstream accuracy generally improves substantially when moving beyond very low dimensions before reaching a plateau, though for GraphSAGE and VERSE, very high dimensions often led to deteriorating performance. But dimensions associated with high stability do not necessarily coincide with those yielding the strongest downstream performance. Using a bootstrap procedure with 10,000 replicates per configuration, the researchers determined the stability-optimal dimension in each replicate and checked whether it fell among the dimensions whose accuracy was within 0.01 of the replicate-specific maximum. Alignment varied substantially across datasets, methods and measures, with disagreement between hard predictions showing the highest alignment with near-optimal performance. Even when alignment was high, however, the exact performance- and stability-optimal dimensions frequently differed, and these mismatches generally persisted across bootstrap replicates, consistent with broad performance plateaus along which stability can continue changing while accuracy remains nearly constant.

The synthetic experiments added a structural dimension to the picture. On Barabási-Albert and Watts-Strogatz networks with fixed density, increasing network size generally shifted both the stability minima and the transition toward stable high-dimensional regimes to larger dimensions for ASNE, node2vec and VERSE, meaning larger networks required higher embedding dimensions before stable regimes were reached. Smaller graphs often exhibited higher stability overall across most dimensions. These patterns were particularly consistent for node2vec and remained broadly visible across both graph models and multiple similarity measures. For DGI and GraphSAGE, by contrast, trends were less consistent. Density told a different story: while on denser graphs ASNE embeddings, and to a lesser extent node2vec and VERSE embeddings, sometimes required larger dimensions before stable regimes emerged, these patterns were not as consistent across graph models and similarity measures as those observed for graph size, and no relationship as systematic as the size effect emerged.

Some subtler results underline how much the choice of stability measure matters. Jensen-Shannon divergence between predicted probability distributions remained at very low levels, commonly between 10^-4 and 10^-2, and showed no recurring dimensionality-dependent trend, even where the stability of hard predictions changed with dimensionality. The authors suggest that low probability divergence does not necessarily imply stable class predictions, since small run-to-run differences can flip predictions near the decision boundary. Similarly, min-max-normalized disagreement failed to reproduce the recurring trends seen for unnormalized disagreement, varying across datasets for all embedding methods. A sensitivity analysis on the Wikipedia dataset, in which hyperparameters were tuned separately at each dimension rather than at dimension 128, did not substantially alter the general dimensionality-dependent trends, though the authors caution they cannot rule out that instability at extreme dimensions partly reflects parameter mismatch rather than training dynamics themselves.

The findings carry practical weight for anyone deploying embeddings in real analyses. For methods such as node2vec, ASNE and DGI, stability often continued improving beyond dimensionality regimes in which downstream performance had already plateaued, potentially incentivizing the use of larger dimensions, though the authors note these apparent benefits would need to be weighed against the increased computational overhead of high-dimensional embeddings. The computational costs are far from trivial: on the CoAuthor dataset, GraphSAGE training exceeded ten hours per embedding at larger dimensions, and link prediction evaluation became infeasible on OGBL-DDI for dimensions above 1024. No single dimensionality regime emerged as universally preferable, and the most suitable dimension may depend not only on predictive performance but also on the relative importance of stability and computational efficiency. The synthetic results further suggest that dimensionality choices should be considered jointly with the intended downstream objective and characteristics of the underlying graph, since dimensionality requirements may increase with network size.

The study also has limitations the authors acknowledge openly. Because they evaluated one implementation per method, they cannot disentangle method-specific from implementation-specific effects on stability, a concern heightened by the fact that the evaluated ASNE implementation differs from the original formulation. The experiments did not extend to very large graphs, and certain trends in very high-dimensional regimes may not have been fully captured. The assessment of representational stability also depends on the chosen similarity measures. Nevertheless, the overall message stands: across five embedding methods, multiple empirical and synthetic datasets, and a broad range of measures, dimensionality can substantially influence embedding stability, often in ways that differ from its effect on downstream predictive performance, and the observed relationships proved highly dependent on both the embedding method and the stability notion considered. The authors suggest future work could develop method-specific theoretical explanations for these patterns and extend the analysis to temporal, signed, heterogeneous and knowledge graphs.

Subject of Research: How embedding dimensionality affects the representational and functional stability of node embeddings across five graph embedding methods

Article Title: The impact of dimensionality on the stability of node embeddings

Article References: Schumacher, T., Reichelt, S., & Strohmaier, M. (2026). The impact of dimensionality on the stability of node embeddings. Applied Network Science, 11(1), Article 59. https://doi.org/10.1007/s41109-026-00830-2

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00830-2

Keywords: node embeddings, graph representation learning, embedding dimensionality, stability, network science, GraphSAGE, node2vec, VERSE, DGI, ASNE, downstream prediction, Applied Network Science