BH-tsNET, FIt-tsNET, L-tsNET:
Fast tsNET Algorithms for Large Graph Drawing

The tsNET [3] algorithm for graph drawing utilizes the popular dimension reduction method t-SNE (t-Stochastic Neighborhood Embedding) [11], which aims to preserve the neighborhood of data points in a low-dimensional projection.

t-SNE models the distances of data points in the high- and low-dimensional spaces as probability distributions. A low-dimensional projection is then computed by minimizing the KL (Kullback-Leibler) divergence [4] between the two probability distributions, typically using gradient descent, by moving the points in the projection according to the gradient of the KL divergence. The runtime of t-SNE is $O(n^2)$, due to the computation of pairwise distances between all pairs of data points.

tsNET uses the graph theoretic distance (i.e., shortest path) between vertices in a graph $G=(V,E)$ as the high-dimensional distance, which takes $O(nm)$ time, where $n=|V|$ and $m=|E|$. Specifically, tsNET adds the following two more terms to the cost function, on top of the KL divergence term used by t-SNE: an $O(n)$-time compression term to accelerate untangling the drawing, and an $O(n^2)$-time entropy term for reducing clutter.

tsNET computes high-quality graph drawings which preserve the clustering and neighborhood structure of vertices. However, it is not scalable to large graphs due to the $O(nm)$ runtime for all-pair shortest path computation and $O(n^2)$ runtime for the cost function.

Recently, fast t-SNE algorithms have been introduced. For example, BH-SNE (Barnes-Hut SNE) [10] utilizes $k$NN ($k$-Nearest Neighbors) and quadtree to reduce the computation of high-dimensional probabilities and KL divergence gradient to $O(n\log n)$ time. More recently, FIt-SNE (FFT-accelerated Interpolation-based t-SNE) [5] utilizes $O(n\log n)$-time approximate $k$NN to compute the high-dimensional probabilities, and a FFT (Fast Fourier Transform) [8]-accelerated interpolation to further improve the runtime of the KL divergence gradient computation to $O(n)$ time.

However, algorithms reducing the overall runtime of tsNET have not been investigated yet. To reduce the runtime of tsNET, there are three $O(n^2)$-time components that need to be reduced: computation of all pair shortest paths, computation of KL divergence gradient, and entropy computation. While it was mentioned as a possible future work to use fast t-SNE algorithms to improve the runtime of the KL divergence term [3], methods to reduce the runtime of the entropy term were not considered yet.

In this poster, we present three new fast tsNET algorithms for drawing large graphs, integrating new fast methods for all-pair shortest path computation and entropy computation, with fast t-SNE algorithms. Specifically, our fast algorithms use a new $O(n)$-time partial BFS method for all-pair shortest path computation.

1. 1.

   The first $O(n\log n)$-time BH-tsNET algorithm uses a new $O(n\log n)$-time quadtree-based entropy computation, integrated with $O(n\log n)$-time quadtree-based KL divergence computation of BH-SNE.

2. 2.

   Faster $O(n\log n)$-time FIt-tsNET algorithm integrates the $O(n\log n)$-time quadtree-based entropy computation with $O(n)$-time interpolation-based KL divergence computation of FIt-SNE.

3. 3.

   The fastest $O(n)$-time L-tsNET algorithm uses a new $O(n)$-time FFT-accelerated interpolation-based entropy computation, integrating $O(n)$-time interpolation-based KL divergence computation of FIt-SNE.

Table 1 summarizes the time complexity analysis of our fast algorithms. For the technical details, see the full version of this poster [7].

We implement BH-tsNET, FIt-tsNET, and L-tsNET in Python using the t-SNE from the scikit-learn library [9], and in C++ based on BH-SNE [10] and FIt-SNE [5]. We use benchmark graphs used in the tsNET evaluation [3] as well as standard test suites commonly used in graph drawing studies: real-world scale-free graphs, biological networks, and mesh graphs. For the details, see the full version of this poster [7].

Extensive evaluation demonstrates that BH-tsNET, FIt-tsNET, and L-tsNET obtain significant runtime improvements over tsNET, on average 93.5%, 96%, and 98.6% respectively. See Figure 1(a).

Surprisingly, our algorithms compute almost the same quality drawings as tsNET, in terms of quality metrics (neighborhood preservation [3], stress [1], edge crossings, shape-based metrics [2]), see Figures 1(b)-(e). Visual comparisons also confirm that our algorithms produce almost the same drawings as tsNET, see Table 2.

Moreover, we compare our algorithms to DRGraph, another linear-time t-SNE-based graph drawing algorithm with a different optimization function. Experiments show that our algorithms perform especially well over DRGraph in visualizing graphs with a regular structure, such as mesh graphs. For the details, see the full version of this poster [7].

Recently, we also presented fast GUMAP algorithms, designed explicitly for graph drawing based on UMAP, which reduce the time complexity from $O(nm)$ to $O(n^2\log n)$ and $O(n)$, utilizing spectral sparsification and edge sampling. For the details, see [6].