Fast Similarity Computation for t-SNE

Data visualization has become a fundamental process of data engineering. t-SNE is one of the most popular data visualization approaches. However, its computation cost is quadratic to the number of data points because it needs to compute similarities for all pairs of data points. One practical way of using t-SNE is random walk-based t-SNE. This approach visualizes user-specified landmark points from the similarities between them based on random walks in a neighborhood graph of data points. It offers two approaches to computing similarities: the direct and analytical approaches. The direct approach approximately computes similarities by explicitly computing random walks in the graph. Unfortunately, it needs to perform numerous random walks for adequate computation accuracy. The analytical approach performs Cholesky factorization on the graph Laplacian and computes exact similarities using the decomposed graph Laplacian. This, however, incurs high computation cost in performing Cholesky factorization. Our proposal, F-tSNE, reduces the computation cost of random walk-based t-SNE by computing the LDL decomposition for the graph Laplacian based on two ideas: (1) reducing non-zero elements in the LDL decomposition by using a reordering matrix and (2) exploiting the sparse structure of the graph when computing the similarities. Theoretically, our approach is guaranteed to yield exact similarities. Experiments show that it is up to 88.4 times faster than the existing alternatives.