Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel (Extended Abstract)

Ye Zhu, Kai Ming Ting

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.

Comparison of t-SNE with Gaussian kernel (left) and Isolation kernel (right) on synthetic data across different parameter settings.

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

Abstract

This paper presents a new insight into improving the performance of Stochastic Neighbour Embedding (t-SNE) by using Isolation kernel instead of Gaussian kernel. We show that Isolation kernel addresses two deficiencies of t-SNE that employs Gaussian kernel, and the use of Isolation kernel enables t-SNE to deal with large-scale datasets in less runtime without trading off accuracy, unlike existing methods used in speeding up t-SNE.
BibTeX
@inproceedings{zhu2022improving,
  author = {Ye Zhu and Kai Ming Ting},
  title = {{Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/812},
}
Figure