In plain words: It first builds a rough map of each point's closest neighbors, then spreads the points across a 2D or 3D chart so neighbors sit near each other. This runs in linear time, handling millions of points faster and more accurately than the usual approach.
Abstract · Visualizing Large-scale and High-dimensional Data
We study the problem of visualizing large-scale and high-dimensional data in a low-dimensional (typically 2D or 3D) space. Much success has been reported recently by techniques that first compute a similarity structure of the data points and then project them into a low-dimensional space with the structure preserved. These two steps suffer from considerable computational costs, preventing the state-of-the-art methods such as the t-SNE from scaling to large-scale and high-dimensional data (e.g., millions of data points and hundreds of dimensions). We propose the LargeVis, a technique that first constructs an accurately approximated K-nearest neighbor graph from the data and then layouts the graph in the low-dimensional space. Comparing to t-SNE, LargeVis significantly reduces the computational cost of the graph construction step and employs a principled probabilistic model for the visualization step, the objective of which can be effectively optimized through asynchronous stochastic gradient descent with a linear time complexity. The whole procedure thus easily scales to millions of high-dimensional data points. Experimental results on real-world data sets demonstrate that the LargeVis outperforms the state-of-the-art methods in both efficiency and effectiveness. The hyper-parameters of LargeVis are also much more stable over different data sets.
Jian Tang, Jingzhou Liu, Ming Zhang, Qiaozhu Mei
arXiv:1602.00370 · cs.LG, cs.HC · submitted Feb 1, 2016 · updated Apr 5, 2016
abstract · pdf · html · WWW 2016
According to the paper, LargeVis improves on Barnes-Hut t-SNE in two ways: first, it uses the idea that "the neighbors of my neighbors are likely my neighbors too" to construct an approximate graph of nearest neighbors in the high-dimensional space in a manner that is computationally much more efficiently than the method used by t-SNE. Second, the authors apparently have found a clever way to use SGD to map this graph to two (or three) dimensions with computational cost linear in the number of nodes.
If the authors release an open-source implementation, LargeVis looks likely to supplant t-SNE as the go-to algorithm for visualizing high-dimensional data.