T HE I MPACT OF D IMENSIONALITY ON THE S TABILITY OF N ODE E MBEDDINGS
arXiv:2604.08492v1 [cs.LG] 9 Apr 2026
Tobias Schumacher University of Mannheim, RWTH Aachen University [email protected]
Simon Reichelt University of Mannheim [email protected]
Markus Strohmaier University of Mannheim, GESIS - Leibniz Institute for the Social Sciences, and Complexity Science Hub [email protected]
A BSTRACT Previous work has established that neural network-based node embeddings return different outcomes when trained with identical parameters on the same dataset, just from using different training seeds. Yet, it has not been thoroughly analyzed how key hyperparameters such as embedding dimension could impact this instability. In this work, we investigate how varying the dimensionality of node embeddings influences both their stability and downstream performance. We systematically evaluate five widely used methods—–ASNE, DGI, GraphSAGE, node2vec, and VERSE—–across multiple datasets and embedding dimensions. We assess stability from both a representational perspective and a functional perspective, alongside performance evaluation. Our results show that embedding stability varies significantly with dimensionality, but we observe different patterns across the methods we consider: while some approaches, such as node2vec and ASNE, tend to become more stable with higher dimensionality, other methods do not exhibit the same trend. Moreover, we find that maximum stability does not necessarily align with optimal task performance. These findings highlight the importance of carefully selecting embedding dimension, and provide new insights into the trade-offs between stability, performance, and computational effectiveness in graph representation learning.
1
Introduction
Graphs are a ubiquitous form of data, with examples including social networks, citation networks, and molecules. The representation of interactions between entities as graphs has enabled researchers to conduct systematic analysis of diverse network systems [16]. For example, social networks have been leveraged for a variety of applications, including the recommendation of friends and content, as well as for advertising purposes. One effective approach for leveraging graphs as features for machine learning techniques is to transform them into node embeddings, which represent the graph as a low-dimensional vector space. The use of embeddings enables the encoding of the relationships and properties of nodes in a manner that allows them to serve as inputs for a variety of downstream tasks, including node classification [3], node clustering [11], visualization [36], and link prediction [34]. For most node embedding methods, a number of sources of randomness are at play, including random initialization, random walks, or stochastic optimization schemes. Consequently, multiple training runs employing the same techniques on the same dataset will produce embeddings that differ from one another. This instability of node embeddings has been documented in the literature [50, 56]. A critical factor for training embeddings, which could also affect the stability of embeddings, is the dimension of the embedding vectors. A dimension that is too small may be unable to capture the structural information of the graph, aiming to compress more information than can fit into small vector spaces. This could also yield unstable embeddings, as different information might get encoded in different training runs. Conversely, a higher dimension allows an embedding to capture more information, but it also adds more computational complexity
Schumacher, Reichelt and Strohmaier
and may lead to overfitting or noise [35]. This study builds upon previous research on stability by investigating the impact of varying embedding dimensions on both the stability and performance of embeddings. In particular, this study seeks to address the question of how embedding dimension influences node embedding stability. We do not consider stability alone but also aim to draw a connection between stability and performance across varying dimensions. Toward that end, we consider five node embedding methods, namely ASNE [33], DGI [55], GraphSAGE [21], node2vec [17], and VERSE [54], and train embeddings of these methods for varying dimensions across several datasets. Across each dimension, we evaluate their stability considering both a representational and a functional angle—for the latter using the outputs of downstream classifiers, of which we also consider the performance. Our results indicate that the stability of node embedding varies across different dimensionalities, both from the representational and the functional perspective. We do, however, observe different patterns across different methods, such as node2vec and ASNE generally increasing their stability with higher dimensionality, which is not less the case for the other methods under study. Further, we find that optimal performance does not always conincide with highest stability. Overall, we believe our work provides novel insight into the choice of dimensionality of network representations. To foster reproducibility, we provide the code of all our experiments online1 .
2
Background
Before describing our experimental framework, we briefly provide background on node embeddings and their stability, including some formal definitions, and summarize related work on the topic. 2.1
Preliminaries
Node Embeddings. Node embedding algorithms map nodes of a given graph to (ideally) low-dimensional vectors in a manner that facilitates subsequent analysis and machine learning tasks by utilizing information from the link structure of the graph as well as, potentially, node and edge features. Formally, we define a graph G as a tuple G = (V, E), where V = (v1 , ..., vN ) is the set of vertices, which, w.l.o.g., we assume to be ordered, and E = (e1 , ..., eM ) is the set of edges in the graph. Then, a node embedding φ : V −→ RD maps each node vi ∈ V to an embedding vector zi = φ(vi ) of dimension D ∈ N. By stacking the embedding vectors, one obtains an embedding matrix Z = [z1 , . . . , zN ]T ∈ RN ×D . Downstream Tasks. After embeddings have been generated, they can be used for downstream tasks such as node classification, link prediction, or graph reconstruction, which we focus on for this study. In node classification, w.l.o.g., it is assumed that each node vi is associated with a label yi ∈ C = {1, . . . , C}, C ∈ N. The goal is then to train a classifier cNC : RD −→ C on the embeddings of individual nodes with known labels for prediction on nodes with unknown labels. Formally, we define the outputs of this classification task as Oi = cNC (zi ) ∈ RC , which we assume to consist of the instance-wise class probability scores for each of the C given classes. Assuming that an ordered set of n ≤ N nodes is classified, these outputs can also be stacked to an output matrix O ∈ Rn×C . In link prediction, the goal is to predict future links based on the current link structure of a graph. This yields a binary classification problem, where corresponding classifiers cLP : RD × RD −→ {0, 1} take as input a pair of node embeddings zi , zj corresponding to the edge ek = (vi , vj ) that is classified. In practice, due to the sparsity of empirical networks, these classifiers are typically trained on all existing (positive) edges within a network, but only use a fraction of non-existing (negative) edges. Within our study, we will overload notation and also denote the output matrix of an ordered set of m ≤ N 2 node pairs as O ∈ Rm×2 . Finally, graph reconstruction can also be considered a link prediction problem, with the only difference being that the task at hand is to correctly predict which edges already exist. Representational and Functional Stability. In line with previous work, we define the stability of an embedding algorithm informally as the difference between two embeddings due to randomness in the embedding algorithm [50]. In this setting, we assume that all training data and hyperparameters are fixed, with only the training seed being different. To analyze the stability of embeddings, we consider two perspectives, namely representational stability, which refers to the differences between two embedding matrices Z, Z ′ , and the functional stability of algorithms, i.e., the differences in the outputs O, O ′ when deploying different embeddings in downstream tasks such as node classification or link prediction. These differences can be quantified via representational similarity measures and functional similarity measures, respectively. We discuss the measures used in this study in Section 3.4, and point to the survey by Klabunde et al. [29] for an in-depth overview of representational and functional similarity. 1
https://github.com/dess-mannheim/dimpact
2
The Impact of Dimensionality on the Stability of Node Embeddings
2.2
Related Work
Research on embedding stability spans multiple domains, and several embedding methods as well as corresponding analyses in the graph domain have been influenced by work on word embeddings. Thus, we briefly summarize results regarding the dimensionality and stability of word embeddings before giving related results for the network embedding domain and summarizing existing research on the relationship between dimensionality and stability across both domains. Dimensionality and Stability of Word Embeddings. Choosing an appropriate dimension can strongly improve the performance of word embeddings [9, 31], and a couple of research efforts have also investigated the problem of selecting the dimension for word embeddings in a principled manner. Most notably, Yin and Shen [64] introduced the PIP loss as a means to select optimal dimensionality. By using this metric to quantify dissimilarity between an oracle embedding and a trained embedding, they identify a bias-variance trade-off in dimensionality selection. Further, they propose an approach to minimize this loss to obtain the optimal dimension of (implicitly) matrix factorization-based word embeddings. Building on this work, Wang [59] proposed a PCA-based approach as a means to determine the optimal dimension of word embeddings in a more direct fashion. The first work pointing out the instability of word embeddings was conducted by Hellrich and Hahn [24], who identified substantial differences in the nearest neighbors of individual words in the embedding space based on different training seeds, with all other parameters and training corpora being fixed. This phenomenon has been confirmed and further analyzed in several studies [2, 5, 10, 13, 32]. Notably, Wendlandt, Kummerfeld, and Mihalcea [60] and Pierrejean and Tanguy [45] have conducted regression analyses to identify factors contributing to the instability of word embeddings and Dridi et al. [13] proposed tuning hyperparameters with respect to stability as a means to improve the quality of embeddings. Node Embedding Stability. The stability of node embeddings has most prominently been analyzed by Schumacher et al. [50] and [56]. Schumacher et al. [50] analyzed the stability of embeddings in terms of geometric stability, i.e., the topological difference in embedding spaces, and downstream stability, i.e., the difference in predictions of downstream tasks, for five embedding algorithms, namely HOPE [42], LINE [53], SDNE [57], node2vec [17], and GraphSAGE [21]. They found that except for HOPE, which yielded nearly constant embeddings, embedding spaces often differed considerably, with GraphSAGE yielding the highest variance in its embeddings. By contrast, performance in downstream tasks remained almost constant, but individual predictions still differed to a larger degree. Wang et al. [56] pointed out similar differences in the geometric stability of LINE, SDNE, node2vec, DeepWalk [44], struc2vec [46], and DNGR [6], and further conducted a regression analysis to identify which factors contribute to embedding stability. They found that both network properties, such as network size, density, or assortativity, and also algorithmic parameters, such as the number and length of random walks for node2vec, had a significant impact on stability. Additional work has analyzed the stability of predictions of end-to-end graph neural networks. Klabunde and Lemmerich [28] also found that aggregate performance remained highly similar, but individual predictions varied substantially. Complementing this work, Shi et al. [51] proposed the graph Gram index as a measure to evaluate the geometric stability of graph neural networks. Finally, [38] recently analyzed stability in knowledge graph embeddings, also finding substantial variation in embedding spaces and individual predictions. Dimensionality of Node Embeddings. In the context of network embeddings, it has also been well-established that the dimension of node embeddings can strongly affect performance in downstream tasks. For instance, Chen et al. [8] and Goyal and Ferrara [16] found that with increasing dimension, performance typically improves until a threshold level is reached, at which point performance either plateaus or deteriorates again. Consequently, there has also been some work aimed at determining the optimal dimension of network embeddings. A line of work has investigated the intrinsic dimensions of networks, pointing out that the number of dimensions necessary to reconstruct a network is typically very low, even for larger real-world networks [1, 4, 41]. These works are, however, mostly aimed at the compression of complex networks rather than building representations that are effective for machine learning tasks. Inspired by the work of Yin and Shen [64] on work embeddings, Gu et al. [19] proposed a principled approach to identify the optimal dimension of network embeddings. Specifically, they adapted the PIP loss to the node embedding domain by introducing a loss based on the deviation of low-dimensional embeddings from embeddings whose dimension corresponds to the number of nodes in the given network—this dimension was considered optimal as it would perfectly encode all network information, as an adjacency matrix does. This loss could then be applied to determine the highest dimensional embeddings which only had an information loss of at most ε compared to this optimal embedding. Further, their systematic analysis on 135 real-world networks "bolstered the idea that the actual number of dimensions that are needed to describe the structure of a network is typically low." We note that their approach, however, requires computing lower-dimensional embeddings before one can evaluate whether it is (close to) optimal. By contrast, Luo et al. [35] proposed the MinGE approach to directly determine the optimal dimension for network representations. Specifically, MinGE is based on minimizing the entropy present in network representations, with entropy modeled as a weighted sum of entropy in graph structure and node features. Their experiments illustrate that GNNs show consistently strong performance in node classification tasks when the dimension of their inner representations corresponds to 3
Schumacher, Reichelt and Strohmaier
the dimension determined by MinGE. The MinGE approach was adapted by [61], who proposed another algorithm based on the minimum entropy principle, in which structural similarity was modeled as a sum of one-dimensional and multi-dimensional structural entropy. Again, the experiments show strong performance of GNN models using the resulting dimensionality for inner layers, although a direct comparison to MinGE is not made. Finally, Dong, Sun, and Liang [12] and Yuki, Suzuki, and Yamanishi [65] proposed embedding models with built-in optimization schemes for dimension selection. The embedding model by Dong, Sun, and Liang [12] is based on missing data imputation, in which dimensions can be selected by their influence on the gradients in model optimization. By contrast, Yuki, Suzuki, and Yamanishi [65] modeled node representations via Gaussian distributions on Riemannian manifolds, where the approach to optimize dimensionality is based on the minimum description length principle [18]. Relationship Between Dimensionality and Stability. In the word embedding domain, a couple of works that analyzed stability also considered the embedding dimension as a factor that potentially drives stability. Leszczynski et al. [32] found that with increasing dimension, downstream stability of several embedding methods would improve up to a plateau, which was reached between dimensions 200 and 400. Similar findings were made considering stability with respect to nearest neighbors in embedding space, where stability also plateaus around dimension D = 300 [5, 10, 13]. For node embeddings, the impact of dimensionality on the stability of node embeddings has only been analyzed on a very peripheral level. In their regression analysis regarding factors influencing stability, Wang et al. [56] considered dimension as a linear predictor in their analysis, for which they found that it had a "moderate significant impact on the stability of embeddings." However, it is not tracked in a more elaborate fashion, and potential non-linear relationships are not explored. Further, Gu et al. [19] in a side analysis briefly evaluated how the stability of node2vec varied across increasing dimensions, finding that variance in these embeddings initially reduced with embedding size, but also slightly started to increase again for high dimensions.
3
Experiments
The objective of this study is to examine the interplay between node embedding dimensionality, stability, and performance across a range of downstream tasks. Moreover, we investigate the influence of graph characteristics and hyperparameters on these relationships. In order to achieve this, we will train embeddings using a range of methods across diverse datasets and assess the stability and performance of each individual dimension. We will then compare the stability and performance of each dimension to determine the effects of dimensionality on stability. This section outlines the methodology employed in our analysis. 3.1
Algorithms
We opted to train node embeddings using a diverse set of algorithms to encompass a variety of methodological approaches, sources of randomness, and factors contributing to instability, while also representing the most widely used embedding techniques. Specifically, we trained embeddings using the following algorithms: • node2vec [17] is inspired by word2vec [40] and DeepWalk [44]. It applies random walks over input graphs to determine which nodes appear in the same context, and then feeds these contexts into the skip-gram model [39]. Sources of randomness are the random walks, the initialization of the skip-gram model, and the negative sampling and optimization when training it. • GraphSAGE [21] applies a graph neural network (GNN) [49] to compute its embeddings. Specifically, nodewise embeddings are formed by iteratively aggregating representations of a sampled subset of each node’s neighbors. The objective function in unsupervised encourages neighboring nodes to have similar representations. Sources of randomness are given by initialization of weights and the neighborhood sampling. • VERSE [54] applies a single-layer neural network which aims to match the distribution of node similarities in the graph with a distribution of embedding similarities. To measure node similarities, different functions such as personalized PageRank [43] or SimRank [26] can be used, while embedding similarity is measured by dot product. Optimization is done using gradient descent with noise contrastive estimation [20], where node embeddings are updated in an iterative fashion. Specifically, at each iteration, one node and one sample from the true similarity distribution, along with a number of negative samples from the noise distribution, are drawn to update embeddings. Along with the random initialization of embeddings, these sampling procedures account for the randomness in VERSE. • Deep Graph Infomax (DGI) [55] adapts the idea of Deep Infomax [25] to the graph domain by maximizing mutual information between individual node embeddings and corresponding high-level summaries of graphs. This is done using a noise-contrastive type objective which trains a discriminator to distinguish pairs of representations and summaries from true and corrupted networks. Node representations are derived by using a 4
The Impact of Dimensionality on the Stability of Node Embeddings
graph convolutional network [27] as encoder, and the input network is corrupted by shuffling node features across instances. Embeddings are trained via gradient descent, where parameters of the GCN encoder and discriminator are updated iteratively. Aside from the shuffling in the node corruption, randomness is also induced in the initialization of the GCN and discriminator weights. • Attributed Social Network Embedding (ASNE) [33] trains a deep neural network architecture which aims to encode link structure of a given network. Specifically, as input it takes each node Vi ’s features along with a one-hot encoding to identify its position, and feeds this information through several layers to return a vector of N node-wise probabilities of a link being formed from vi to target node vj . Embeddings are then taken from the last inner layer. Aside from the initialization of the neural network, further sources of randomness are provided by negative sampling and dropout schemes in the model optimization. For GraphSAGE and DGI, we used the implementation provided in PyTorch Geometric [14, 15]. For node2vec, we used the implementation from grape [7], and for ASNE, we resorted to the karateclub package [48]. Finally, for VERSE, we used the reference implementation by Tsitsulin et al. [54]. 3.2
Datasets
In order to analyze the effect of various graph properties on the relationship between dimension, stability, and performance, we are training embeddings on a broad rang of datasets. Empirical Datasets In the following, we briefly describe the empirical datasets used in this study. An overview of the these datasets and their properties is also provided in Table 1. • Cora [63] is a network of scientific papers. Each node represents a paper, and two nodes form an undirected edge if one of the corresponding papers cites the other. Node features are given by bag-of-words representations of the underlying document text, and node labels correspond to topical categories of papers. • PubMed [63] is a citation network, comprising papers from the biomedical domain. As for Cora, nodes represent papers with links being formed if one paper cites another, node features correspond to bag-of-words representations, and node labels to topical categories. • Wikipedia is a network of articles connected by hyperlinks. Each node represents an article, with edges linking articles that reference each other [62]. • BlogCatalog is a social network of bloggers, where nodes represent individual users, and edges denote interactions or friendships. The dataset has been used extensively for community detection and social network analysis [62]. • Facebook [47] is a page-page graph of verified Facebook sites. Nodes correspond to Facebook sites, links are formed if pages mutually liked each other. Node features were extracted from site descriptions, and node labels correspond to site categories. Cora, PubMed, Wikipedia, BlogCatalog and Facebook were sourced from PyTorch Geometric. We evaluated downstream performance in terms of node classification. For Cora and PubMed, we used existing benchmark splits into training, validation and test data. For BlogCatalog, Facebook and Wikipedia, we sampled fixed training, validation and test sets, by splitting the node set into at 70% training, 10% validation and 20% test data. 3.3
Experimental Setup
For our main experiments on empirical datasets, we varied the dimensionality across the values D ∈ {2i , i ∈ {2, 3, . . . , 12}}, and always computed 30 embeddings per dimensionality, algorithm, and dataset. To ensure the
Table 1: Overview of empirical datasets. Features indicates the number of node features that can be used as inputs for embedding models, Classes indicates the number of different target classes in the downstream classification problem. Dataset Nodes Edges Features Density Classes Cora PubMed Facebook Wikipedia BlogCatalog
2,708 19,717 22,407 2,405 5,196
10,556 44,338 342,004 17,981 343,486
5
1,433 500 128 4,973 8,189
0.0029 0.0002 0.0014 0.0062 0.0254
7 3 4 17 6
Schumacher, Reichelt and Strohmaier
quality of embeddings, we performed some basic parameter tuning on all datasets, evaluating the performance of the dataset-specific downstream tasks. For all algorithms, we only tuned parameters on dimensionality D = 128, since the dimension of embeddings does not affect the corresponding loss functions—differences in performance would then be due to different constraints in dimensionality when the same information is processed. More details on parameter tuning can be found in Appendix A. 3.4
Evaluation
In our analyses, we need to evaluate the representational and functional stability of embedding models. In the following, we briefly describe how the corresponding evaluations are conducted. Representational Stability. Following previous work [50], we selected aligned cosine similarity [23], k-NN Jaccard similarity [24], and second-order cosine similarity [22] to evaluate representational stability. In addition, we considered distance correlation [52], since this measure performed well consistently in the ReSi benchmark for representational similarity measures [30]. Aligned cosine similarity is based on aligning embeddings by solving the orthogonal Procrustes problem, where the aim is to find the best orthogonal mapping to rotate these embeddings onto each other. Specifically, the goal is to find the orthogonal matrix Q∗ := argminQ∈O(D) ∥ZQ − Z ′ ∥F , (1) where O(D) denotes the orthogonal group of dimension D and ∥ · ∥F the Frobenius norm. After aligning embeddings via Q∗ , one can then consider the cosine similarities between all instance representations after alignment, and use their average as similarity score: PN mAlignCos (Z, Z ′ ) = N1 i=1 cos-sim (zi Q∗ , zi′ ) . (2) Distance correlation avoids potential issues in finding optimal alignments by considering the similarity of all individual node embeddings zi , zj to each other. These differences are collected in a representational similarity matrix (RSM) S ∈ RN ×N , which can be defined in terms of its elements via Si,j := s(zi , zj ),
(3)
where s : RD × RD −→ R denotes a given instance-wise similarity function. Assuming that RSMs are meancentered in both rows and columns, one can use their squared sample distance covariance dCov2 (S, S ′ ) = PN PN 1 ′ i=1 j=1 Si,j Si,j as similarity function s, and derive the distance correlation via N2 r dCov2 (S,S ′ ) . (4) mDistCorr (Z, Z ′ ) = √ 2 2 ′ ′ dCov (S,S) dCov (S ,S )
Finally, k-NN Jaccard similarity and second-order cosine similarity are based on comparing the nearest neighbors of instances in the representation space. Both measure determine the sets of k nearest neighbors NZk (i) of each node embedding zi from the full network embedding Z with respect to cosine similarity, and then compute vectors of instance-wise neighborhood similarities vNN (Z, Z ′ ) ∈ RN , which are averaged over all instances to obtain similarity measures for the full embeddings Z, Z ′ : PN mNN (Z, Z ′ ) = N1 i=1 vNN (Z, Z ′ )i . (5) For the k-NN Jaccard similarity, this vector simply contains the Jaccard similarities of the nearest neighbors of each pair of corresponding instance representations zi and zi′ : |N k (i)∩N k (i)| k (6) vJaccard Z, Z ′ i := |NZk (i)∪NZk ′ (i)| . Z
Z′
Second-Order cosine similarity considers the union of the instance-wise nearest neighbors in terms of cosine similarity as an ordered set {j1 , . . . , jK(i) } := NZk (i) ∪ NZk ′ (i), and then compares these cosine similarities to the nearest neighbors via k ′ ′ v2nd-Cos Z, Z ′ i := cos-sim Si,j1 , . . . , Si,jK(i) , Si,j , . . . , Si,j , 1 K(i) where S, S ′ denote the RSMs w.r.t. cosine similarity. We note that the first two measures, aligned cosine similarity and distance correlation, consider similarity from a global perspective–—either the embeddings of the whole network need to be aligned, or the correlations across the full RSMs 6
The Impact of Dimensionality on the Stability of Node Embeddings
are evaluated. Conversely, k-NN Jaccard similarity and second-order cosine similarity evaluate similarity from a local perspective, as they only consider differences in the immediate neighborhood of the embeddings of individual nodes. Functional Stability. In line with previous work [28, 50], we evaluate functional stability of node embeddings mainly in terms of variance in the individual predictions resulting from downstream tasks, since variability in aggregate performance scores (e.g., accuracy, F1 scores) has been shown to be low. Specifically, we consider disagreement, min-max-normalized disagreement, the stable core, and Jensen-Shannon divergence. Disagreement [37] corresponds to the rate of conflicting predictions between two outputs. Letting O, O ′ ∈ Rn×C denote the output predictions resulting from two embeddings (as defined in Section 2.1), disagreement can be defined as PN ′ }. (7) mDis (O, O ′ ) = N1 i=1 1{arg maxj Oi,j ̸= arg maxj Oi,j Given that disagreement is implicitly bounded by the actual error rates of the embedding models, we further consider the min-max-normalized disagreement as proposed by Klabunde and Lemmerich [28], which relates the observed disagreement mDis (O, O ′ ) to the minimum and maximum possible disagreement, given the error rates qErr (·) of (min) the models. The minimum is computed as mDis (O, O ′ ) = |qErr (O) − qErr (O ′ )|, and the maximum possible (max) ′ disagreement as mDis (O, O ) = min(qErr (O) + qErr (O ′ ), 1), leading to the measure mMinMaxNormDis (O, O ′ ) =
(min)
mDis (O,O ′ )−mDis (max)
mDis
(O,O ′ )
(min)
(O,O ′ )−mDis
(O,O ′ )
.
(8)
Disagreement only operates on pairs of outputs, however, pairwise similarity of outputs does not imply similarity within a larger group of outputs O := {O, O ′ , O ′′ , . . . }. Thus, we also consider the stable core [50], which corresponds to the fraction of instance-wise predictions that agree across the whole group of outputs: PN ′ mSC (O) = N1 i=1 min O,O′ ∈O 1{arg maxj Oi,j = arg maxj Oi,j }. (9) s.t. O̸=O ′
Finally, we also include a measure that evaluates differences in the class-wise probability score rather than the pure hard predictions. Specifically, we consider the average Jensen-Shannon Divergence (JSD) across all instance-wise predictions. Letting KL(·∥·) denote the Kullback-Leibler divergence, the resulting measure is defined as PN 1 ′ (10) mJSD (O, O ′ ) = 2N i=1 KL(Oi ∥O i ) + KL(Oi ∥O i ), ′
where O = O+O denotes the average output matrix. 2
4
Results
In the following we present our results. We begin with downstream performance, before analyzing the impact of dimension on representational and functional stability. 4.1
Downstream Performance
We begin by analyzing the downstream performance across varying dimensions, which are presented in Figure 1, where we use a logistic regressor as downstream classifier. We present results with a MLP as downstream classifier in Appendix B. In line with previous work, we observe that with increasing dimension, performance generally tends to improve up to a plateau level. This effect is most consistent for node2vec and ASNE embeddings, which reach their plateaus mostly around dimensions 256-512. For DGI, such plateaus are not necessarily reached, as on most datasets performance still increases up to dimension 4096. Interestingly, the Wikipedia dataset is the only exception here, where performance even decreases after D = 1024. This dataset also yields particularly strong decreases for VERSE and even more for GraphSAGE, though for these embedding methods, we observe a general tendency of decreasing performance after an optimal dimension has been reached. Finally, it is of note that for Wikipedia and BlogCatalog, which are particularly rich in the number of features, performance is the worst when embedding methods like node2vec and VERSE are used that do not encode such node information. 4.2
Representational Similarity
For representational similarity, we both consider the local perspective in terms of k-NN Jaccard similarity, and the global perspective in terms of distance correlation. Results with respect to second-order cosine similarity and aligned cosine similarity are provided in Appendix B—these are largely in line with the two measures presented here. 7