Abstract
t-Distributed Stochastic Neighbour Embedding (t-SNE) is a widely used technique for high-dimensional data visualization. However, its reliance on the data-independent Gaussian kernel leads to two significant drawbacks: structural misrepresentation of complex data and high computational costs due to the need for per-point bandwidth (perplexity) optimization. This paper proposes IKt-SNE, which replaces the Gaussian kernel with a data-dependent Isolation Kernel. By leveraging a partition-based approach, the Isolation Kernel naturally adapts to local data density, eliminating the need for expensive perplexity searches. Experimental results on synthetic and real-world datasets demonstrate that IKt-SNE not only provides more accurate structural representations but also achieves up to an 80x speedup in similarity calculations for large-scale datasets.
Introduction
t-SNE is considered the gold standard for visualizing high-dimensional data. Despite its popularity, it suffers from two "Achilles' heels" stemming from its use of the Gaussian kernel to measure high-dimensional similarity. First, the Gaussian kernel is data-independent, requiring a unique bandwidth for every data point (controlled by the perplexity parameter) to capture local structures. This often fails when clusters have varying densities or share common points. Second, calculating these individual bandwidths is computationally expensive, leading to $O(n^2)$ complexity that hinders scalability for large datasets.
Methodology
The proposed IKt-SNE replaces the standard Gaussian kernel with the Isolation Kernel. Unlike the Gaussian kernel, the Isolation Kernel is partition-based. It divides the data space into cells using random partitions based on a small data subsample (parameterized by $\psi$). Similarity is defined by the frequency with which two points fall into the same partition across multiple iterations.
This mechanism allows the kernel to be inherently density-aware—creating smaller cells in dense regions and larger ones in sparse regions—without requiring per-point parameter tuning. The remainder of the t-SNE pipeline, including the low-dimensional Student-t distribution and KL-divergence optimization, remains unchanged. This simple swap allows the algorithm to capture global distributional information that point-based kernels ignore.
Results and Discussion
The effectiveness of IKt-SNE was evaluated using synthetic 50-dimensional datasets and real-world benchmarks like COIL20. A key test involved a synthetic dataset with five subspace clusters sharing a common origin point.
As shown in the figure above, standard t-SNE with a Gaussian kernel (left column) fails to correctly represent the relationship between the origin point ('x') and the five clusters, typically associating the origin with only one cluster. In contrast, IKt-SNE (right column) correctly positions the origin point at the intersection of all clusters, accurately reflecting the high-dimensional geometry. This density awareness is built into the Isolation Kernel's partitioning mechanism.
Furthermore, IKt-SNE offers a massive computational advantage. On a dataset of 100,000 points, the Isolation Kernel similarity calculation took 887 seconds, compared to over 20 hours (72,196 seconds) for the Gaussian kernel—a speedup of approximately 80x. This efficiency is achieved without relying on the approximation shortcuts used in variants like FIt-SNE, which can sacrifice accuracy for speed.
Conclusion
By substituting the Gaussian kernel with the Isolation Kernel, IKt-SNE addresses the fundamental limitations of traditional t-SNE. It provides a more robust, density-aware representation of complex data structures while significantly reducing computational overhead. Future work includes integrating the Isolation Kernel into existing fast t-SNE frameworks to further enhance performance and exploring its sensitivity to the $\psi$ hyperparameter.
Summary updated