Computer Graphics and Visualization • Publications

IEEE Transactions on Visualization and Computer Graphics

An Efficient Dual-Hierarchy t-SNE Minimization

Mark van de Ruit, Markus Billeter, and Elmar Eisemann

Our method leverages a pair of spatial hierarchies over the embedding (center right) and a field (far right) over the embedding space to accelerate t-SNE minimization. Progression of minimizations (left) using these hierarchies is shown for a 60K point MNIST dataset (top) and a 1.2M point ImageNet dataset (bottom). The hierarchies are visualized for the last iteration of minimization.

t-distributed Stochastic Neighbour Embedding (t-SNE) has become a standard for exploratory data analysis, as it is capable of revealing clusters even in complex data while requiring minimal user input. While its run-time complexity limited it to small datasets in the past, recent efforts improved upon the expensive similarity computations and the previously quadratic minimization. Nevertheless, t-SNE still has high runtime and memory costs when operating on millions of points. We present a novel method for executing the t-SNE minimization. While our method overall retains a linear runtime complexity, we obtain a significant performance increase in the most expensive part of the minimization. We achieve a significant improvement without a noticeable decrease in accuracy even when targeting a 3D embedding. Our method constructs a pair of spatial hierarchies over the embedding, which are simultaneously traversed to approximate many N-body interactions at once. We demonstrate an efficient GPGPU implementation and evaluate its performance against state-of-the-art methods on a variety of datasets.

More Information

Publisher Paper preprint Supplemental

Citation

Mark van de Ruit, Markus Billeter, and Elmar Eisemann, An Efficient Dual-Hierarchy t-SNE Minimization, IEEE Transactions on Visualization and Computer Graphics, 28, pp. 614–622, 2022.

BibTex

@article{bib:van de ruit:2022,
    author       = { van de Ruit, Mark and Billeter, Markus and Eisemann, Elmar },    
    title        = { An Efficient Dual-Hierarchy t-SNE Minimization },
    journal      = { IEEE Transactions on Visualization and Computer Graphics },
    volume       = { 28 },
    year         = { 2022 },
    pages        = { 614--622 },
    doi          = { 10.1109/TVCG.2021.3114817 },
    dblp         = { journals/tvcg/RuitBE22 },
    url          = { https://publications.graphics.tudelft.nl/papers/81 },
}