Hyperbolic t-SNE with a Quadtree Splitting in the Cartesian Coordinate System

Abstract

With the rapid growth in data collection, efficient data processing is critical. Dimensionality reduction methods, like t-distributed stochastic neighbour embedding (t-SNE), compress high-dimensional data into embeddings that preserve the key features of the datasets making data less sparse and easier to process further. Recent improvements suggest that using hyperbolic space for data representation can benefit embeddings. As it is a new technique, it remains computationally expensive. Previous work suggests that a Barnes-Hut approximation with a polar quadtree can be applied to the Poincaré disk model to approximate the result of hyperbolic t-SNE and accelerate its calculation. However, the polar quadtree is proposed as a solution to accelerate the calculation without exploring alternative approaches. Aiming to close this gap, we propose an acceleration method using Barnes-Hut approximation with a Cartesian quadtree. We experimentally compare our acceleration method to a polar quadtree and showcase its lower execution time without the loss of quality of the embeddings.
Implementation and scripts for the experiments and plots are available at https://github.com/Sne4kers/hyperbolic-tsne