Optimizing graph layout by t-SNE perplexity estimation

Kruiger et al. [6] demonstrated that their employment of t-SNE, named tsNET, outperforms several other DR algorithms like IDMAP in graph layout, where tsNET simplifies the input parameter settings to focus on perplexity only with minimal tuning of other parameters such as learning rate and number of iterations. Based on tsNET, tsNET* initializes a layout using PivotMDS, and optimizes the layout based on the PivotMDS layout. It is mentioned that the perplexities were set on average of 80 with a standard deviation of 45 for most of the test datasets. However, it has not been discussed how perplexity for each dataset was selected (except EVA dataset) and if different perplexity affects the graph layout, tsNET rejects small perplexity as input.

Xu et al. [7] drew graphs using a model named t-NeRV [16], which was a generalized t-SNE model based on a modified graph-theoretic distance matrix, in which the cost function is a combination of the average of both of the Kullback–Leibler divergence from high-dimensional space to low-dimensional space and vice versa, the cost of one of the energy model out of a modified Kamada and Kawai (KK) model, a modified Fruchterman-Reingold (FR) model, and a modified Linlog model. Their approach also showed that the output graph layout is quite dependent on the fine-tuning of a set of parameters controlling early compression, adjacent neighbor compression, node repulsive forces, and edge attractive forces during the cost computation. Again, how the perplexity was selected for different results presented in the paper has not been mentioned.

In addition to drawing graph based on the graph-theoretic distances, a parametric version of t-SNE named GraphTSNE [8] adopted additional node features in the final graph layout. GraphTSNE trains a two-layer residue gated graph convolutional network using a modified t-SNE cost \(C_T\) consisting of both the graph clustering loss \(C_G\) and the feature clustering loss \(C_X\), so that \(C_T = \alpha C_G + (1-\alpha ) C_X\). The graph clustering loss is computed based on the shortest graph-theoretic distance, while the feature clustering loss is computed based on the Euclidean distance of word embedding of each node. An important learning goal is to optimize the trade-off weight \(\alpha \) for the two loss components, and the perplexity is set to 30. However, when tested with tsNET, the CORA dataset works when the perplexity is set bigger than 169. The impact of different perplexities in GraphTSNE has not been investigated.

We can observe that the perplexity initialization of the use cases mentioned above shows randomness. As a fact, optimization of perplexity has raised attention of some researchers. De Rosa et al. [17] investigated several perplexity meta-heuristic optimization methods including artificial bee colony algorithm, bat algorithm, genetic programming, and particle swarm optimization on word embedding visualization. A practical issue is that the optimization methods are evaluated by the Kullback–Leibler divergence cost residue, which is closely related to perplexity itself. That means different perplexities correspond to different cost when initializing, the cost residues for different perplexities are not comparable. De Bodt et al. [18, 19] tried perplexity-free parametric t-SNE, and also tried to adjust the embeddings (visualization) by using additional class labels instead of the traditional perplexity [20]. Their methods introduced supervised training process. As in our case, t-SNE will be employed for unsupervised DR, we will first investigate the impact of different perplexities on graph layout quality, then test our approach to estimate appropriate value of this parameter on benchmark datasets.

The perplexity in t-SNE is 2 to the power of Shannon entropy of the conditional distribution induced by a data point \(x_i\) (see Eq. 1). As explained by Maaten [14], “the perplexity of a fair die with k sides is equal to k. In t-SNE, the perplexity may be viewed as a knob that sets the number of effective nearest neighbors. It is comparable with the number of nearest neighbors k that is employed in many manifold learners.”whereandwhere \(p_{j\vert i}\) is the conditional probability of data point \(x_j\) in the neighborhood of \(x_i\) based on a Gaussian distribution. t-SNE defines joint probabilities \(p_{ij}\) by symmetrizing the two conditional probabilities as follows:Note that the bandwidth of the Gaussian kernels, i.e., \(\sigma _{i}\) in Eq. 3, is set in a way that \(H(P_i)\) equals a predefined perplexity [15]. In addition, \(\sigma _{i}\) is different for each data point \(x_{i}\), which means that it changes for each high-dimensional instance in order to capture the variations in density for different high-dimensional neighborhoods, where \(\sigma _{i}\) tends to be smaller in regions of the data space with a higher data density compared to the regions with lower density [15]. In practices, \(\sigma _{i}\) is found iteratively by trial-and-error [21], using binary search, until a user-defined perplexity H is reached. With this process the probability matrix P in the high-dimensional space is obtained. Similarly, the probability matrix Q in the low-dimensional space based on t-distribution is computed asThen, Kullback–Leibler divergence \(C_{\mathrm{KL}}\) as cost is computed to minimize the difference between P and Q, usually by gradient descent.With an underestimated perplexity or the unfounded Gaussian kernel after limited iterations, the data points in the defined neighborhood fail to fit to a Gaussian, resulting in exceptions with undefined \(p_{j\vert i}\). We discuss our solution to this issue in Sect. 3.1.

Espadoto et al. [12] summarized most widely used metrics for graph layout evaluations. Quality metrics include scalar metrics (trustworthiness, continuity, normalized stress, neighborhood hit, visual separation metrics), local metrics (projection precision score, stretching and compression, average local error), and point-pair metrics. As we would like to keep in line with the work of tsNET and tsNET* [6], the graph layout in this paper is evaluated exactly the same as [6] by (1) normalized stress measurement \(M_{\sigma }\), (2) neighborhood preservation measurement \(M_{np}\), and (3) visual inspection. Below, we list the formal definitions of normalized stress and neighborhood preservation in [6]. As the visual inspection is not a quantitative metric, we are not able to define it as a metric similar to the other two measurements. Instead, we evaluate a visualization by inspecting the structural distortion or overlapping on the benchmark datasets.

We make modification based on the Python code available from t-SNE Github [14] to improve handling of exceptions during bandwidth fitting.

Handling exceptions may vary in practices. The original standard t-SNE code based on which we have been working does not accept underestimated perplexities, neither does tsNET. For example, tsNET simply throws the exceptions in case an underestimated perplexity is fed, an increased user-defined perplexity is then expected to try again until it works. It is a reasonable solution in practice, as an increased perplexity means considering a broader neighborhood with more samples for more reliable statistical results. However, the randomness in this perplexity initialization procedure seems to be quite user-unfriendly, especially for some extreme examples like the EVA dataset, which needs almost 600 as the perplexity to start off in tsNET [6].

As we identify that the exceptions are caused by data sparsity, we apply two strategies as solutions to the problem. One strategy is to increase the Gaussian kernel \(\sigma _i\) by a controlled exaggeration rate during the process to find an appropriate \(\beta _i\), where \(\beta _i\) is a function of \(\sigma _i\), \(\beta _i = \frac{1}{2\sigma _i^2}\), in order to avoid failures when fitting the data points. The exaggeration rate is 2 in our experiment.

Another strategy is to run an intrinsic grid search within limited steps for a bigger perplexity. When detecting an exception during fitting without updating the initial exaggeration rate of Gaussian kernel, the perplexity is increased by a pre-defined rate, which is currently 3 in our experiment. The modifications are described in algorithm 1.

The two strategies are applied in different situations to ensure the delivery of an output. Generally, the perplexity strategy works for all kinds of datasets. However, as the intrinsic grid search process for a big dataset is time-consuming, the Gaussian kernel strategy can be considered to deliver a result with any perplexity initialization. In our following experiments, the Gaussian kernel strategy is applied to large graphs, and perplexity increase strategy is applied to small graphs.

First of all, we would like to identify the relationship between a perplexity and the graph layout quality measured by the normalized stress, neighborhood preservation, and visualization that directly reflects the global connective structure.

The concept of “large” and “small” in terms of perplexity is dependent on the size of dataset; therefore, we map the value of perplexity to a specific percentage of the dataset size. The t-SNE perplexity defines the size of neighborhood within which the data points are considered. Based on the above discussion, we propose the following hypothesis:

Hypothesis: A relative smaller perplexity will generate a graph layout with both higher normalized stress and more neighborhood preservation, while a larger perplexity will generate a graph layout with both lower normalized stress and less neighborhood preservation.

As a higher normalized stress means more overall information will be lost from a global perspective, and a higher neighborhood preservation means neighborhood information can be preserved with a higher precision from a local perspective, and vice versa, a further question based on the hypothesis is, how to find the balance between a perplexity and graph layout quality measured by the two metrics. We propose our perplexity estimation approach by considering the size of dataset, the distribution of input data, and the graph density, which is illustrated as follows.

Given a graph G(V, E), the Gaussian mean \((\mu )\) and kernel \((\sigma )\) of the graph-theoretic distances of G is obtained at first. Then, we estimate a reasonable perplexity perp according to the dataset size \(\vert V\vert \), graph density \(d = \vert E\vert / \vert V\vert \), \(\mu \) and \(\sigma \) of the Gaussian, which can be described as:where \(\delta (d)\) can be regarded as the graph density regulator, as the graph density d is considered as a positively correlated factor of perplexity in addition to the dataset size, a small or large d corresponds to a small or large perplexity, respectively.

The idea behind the upper part of the perplexity selection in Eq. 9 is that the statistical result for small sized data is less reliable compared to relative large sized data. Therefore, we can set a fixed number as the perplexity. The idea behind the bottom part of the selection method can be explained from three aspects. First, the perplexity can be bigger for large dataset, smaller for small dataset, then the dataset size \(\vert V\vert \) is a direct factor when choosing a perplexity. Second, the perplexity can be bigger for more densely distributed data, whereas a smaller perplexity works for sparsely distributed data. This factor can be measured by how far the Gaussian distribution spreads considering the neighborhood far away, i.e., \(\frac{\mu - 2\sigma }{\mu }\). Finally, the perplexity is regulated by the graph density regulator \(\delta (d)\).

Moreover, we also consider the runtime issue. The runtime on large datasets such as graphs with over 2000 vertices are reported over several hundreds of seconds when applying tsNET and tsNET* (see Table 4 in [6]), similar trend about runtime for our modified version of the standard t-SNE is also expected. In the current Python environment, an accelerated t-SNE version, sklearn Barnes–Hut TSNE, is available by implementing Barnes–Hut approximations, allowing the tool to be applied on large real-world datasets [15].

We then adapt our perplexity estimation to sklearn Barnes–Hut TSNE by updating Eq. 9 as:The adaption to sklearn Barnes–Hut TSNE in Eq. 10 is expected to work on the large datasets for accelerating purpose without losing too much precision. We test all the proposed methods in the following experiments.

We test our approach with the 20 datasets released by the tsNET team [22]. Table 1 lists the datasets.

In order to analyze the results, we label the datasets regarding their size and graph density. Small and large graphs refer to graphs with less than 1000 and more than 1000 vertices, respectively. Sparse and dense graphs stand for graphs with graph density less than 3 and more than 3, respectively, where the graph density is calculated by \(\vert E\vert /\vert V\vert \).

We carry out a series of tests to validate hypothesis. The perplexity is set as 2%, 5%, 10%, 20%, 30%, 40% and 50% of the size of individual dataset. Figure 1 shows the boxplot of \(M_{np}\) and \(M_{\sigma }\) over the 20 datasets, where the mean value of each subgroup labeled by the percentage is dotted.

Figure 1b shows that the average neighborhood preservation \(M_{np}\) increases to the peak when perplexity is less than 10% of dataset size, then decreases with the increase in perplexity. The average normalized stress \(M_{\sigma }\) in Fig. 1a increases to the peak when perplexity is less than 5% of dataset size, then decreases with the increase in perplexity. However, the decrease in \(M_{\sigma }\) is less sharp than the \(M_{np}\), as shown in Table 2 where the linear model coefficient \(\mathrm{lm}\_\mathrm{coef}\) of \(M_{\sigma }\) and \(M_{np}\) is \(-\,4.3826\) and \(-\,6.1940\), respectively. If we flip over one of the fitted lines against the x-axis, the intersection point of the two lines can be identified when \(x=0.4664\). It indicates that a large perplexity no more than 47% of the dataset size could result in quite stable visualization in which both normalized stress and neighborhood preservation could be more likely to be well-balanced. The correlation between pairs of variables is presented in Table 2. Pearson’s correlation coefficient presented as cor_coef suggests that both of the average \(M_{np}\) and the average \(M_{\sigma }\) are significantly negatively correlated to perplexity, with correlation coefficient − 0.8299 and − 0.9450, respectively, both are very close to − 1. The results strongly support the hypothesis that a smaller perplexity corresponds to a larger \(M_{\sigma }\) and a larger \(M_{np}\), and that a larger perplexity corresponds to smaller \(M_{\sigma }\) and \(M_{np}\). In addition, the smoothed quadratic means of both \(M_{\sigma }\) and \(M_{np}\) shown in Fig. 2, which are fitted in R by loess method and formula \(y \sim x\), is also a strong visual support to the hypothesis.

To illustrate the issue visually with examples, Fig. 3 demonstrates two datasets with gradually increased perplexities ranging from 2 to 100% of the dataset size using the modified standard t-SNE. We can see that the visualizations generated with a larger perplexity are fairly robust from a global perspective (less \(M_{\sigma }\)), meanwhile preserving neighborhood information with less precision (less \(M_{np}\)) as more nodes are overlapped with the increase in perplexity.

We also examine the tsNET and tsNET* visualizations using their released code with the change of perplexities the same as in Fig. 3, which is shown as Fig. 4. The maximal iteration number is set 1100 for all tests presented in Fig. 3 and Fig. 4. A similar trend as Fig. 3 presented can be inspected from the graph layouts presented in Fig. 4 that tsNET and tsNET* visualizations generated with a larger perplexity are quite robust from the global perspective. However, the nodes of dw_1005 in tsNET and tsNET* layouts with a larger perplexity are much compressed with the increase in perplexity before 20% of the dataset size, and spread out with less overlapping with the increase in perplexity after 30% of the dataset size, which is different from what we can observe in Fig. 3, most probably due to the additional control of node repulsion and edge attraction in tsNET [6].

Overall, we can identify the descending trends of both \(M_{np}\) and \(M_{\sigma }\) with the increase in perplexity in Fig. 1, with which the hypothesis can be validated. In addition, as shown in Table 2, \(M_{np}\) and \(M_{\sigma }\) are positively correlated with \(p = 0.63\), it suggests that there is a need to find a trade-off between \(M_{np}\) and \(M_{\sigma }\) with respect to an appropriate perplexity, which will be large enough to generate a good layout with less \(M_{\sigma }\), but small enough to preserve more neighborhood details with higher \(M_{np}\).

We test our perplexity estimation approach with the 20 datasets. The perplexity is set according to Eq. 9, with the fixed value 40 as perplexity for small sized graphs. The threshold is 1000. Further, we roughly set the value of \(\delta (d) \in \{0.1, 0.3\}\) in our experiment as described in Eq. 12, and only apply a big \(\delta (d)\) value to large and very dense graphs to avoid overfitting.

In our approach, we estimate the value of perplexity based on the normality of the input data, which is very effective when tested on the benchmark datasets. We also notice that each test dataset is a connected component such that the distribution of pairwise graph-theoretic distances fits normality well. For graphs with many disconnected components, a layout with much higher stress is supposed to be generated by t-SNE, as pilot experiments show, and similar findings is also reported in the work [7]. Focusing on the largest connected component or the connected component of interest is a practical solution to employ t-SNE on graphs with many disconnected components.

We estimate the value of perplexity for small sized graph with less than 1000 nodes to 40, which is an approximation between 2 and 10% of 1000, based on the average graph size of the test data. An increased value of graph density regulator \(\delta (d)\) is not applied to the small graphs to avoid overfitting, whose visualizations show more randomness/uncertainty than the large graphs due to the data sparsity. In our experiment, we observe an automatic increase in perplexity from 40 to 100 for the small dense dataset jazz, and it shows the robustness of our approach.

Our approach presents advantages with respect to ease of use and effectiveness.

First, our approach does not require users to try multiple times with different perplexities as input to deliver the acceptable output, which is very easy to use. For example, the EVA dataset can be visualized with any smaller perplexities compared to 600 in tsNET and tsNET*, as shown in Fig. 6. However, an extra grid search could probably help to find an optimum with extra costs of time and effort.

Second, our approach does not rely on the t-SNE parameter tuning such as the weight of the compression term [6, 7], and it does not require an additional PivotMDS layout as initialization as tsNET* does, although the employment of a PivotMDS layout seems to be beneficial for small graphs as tested. As the tsNET* works based on the initialization of PivotMDS layouts, t-SNE cannot obtain better embeddings in case the PivotMDS layouts could not fully reflect the relations based on graph-theoretic distances.

Experimental results show that our approach is very effective to visualize graph data with good quality evaluated by normalized stress, neighborhood preservation and visual inspections, as well as a significant improvement in runtime when applied with sklearn Barnes–Hut TSNE on large datasets without losing visualization quality. Our work is a step beyond the work of Kruiger et al. [6] and Wattenberg et al. [13], and it not only reveals the impact of t-SNE perplexity on graph layouts, but also presents guidelines to estimate an appropriate perplexity for good layout, and offers possibility to accelerate the process using widely used Python tools.