Breaking the curse of dimensionality with Isolation Kernel

Kai Ming Ting, Takashi Washio, Ye Zhu, Yang XuarXiv 2021 · OpenReview

Abstract

The curse of dimensionality has been studied in different aspects. However, breaking the curse has been elusive. We show for the first time that it is possible to break the curse using the recently introduced Isolation Kernel. We show that only Isolation Kernel performs consistently well in indexed search, spectral & density peaks clustering, SVM classification and t-SNE visualization in both low and high dimensions, compared with distance, Gaussian and linear kernels. This is also supported by our theoretical analyses that Isolation Kernel is the only kernel that has the provable ability to break the curse, compared with existing metric-based Lipschitz continuous kernels.

Introduction

In machine learning, the "curse of dimensionality" often manifests as the concentration of measure. In high-dimensional spaces, the geometric distance between any two randomly chosen points tends to become almost identical. If every point in a dataset is roughly the same distance from a query point, the concept of a "nearest neighbor" becomes mathematically meaningless. Traditional metric-based Lipschitz continuous kernels, such as the widely used Gaussian/RBF kernel, and standard Euclidean distance fail in these settings, leading to performance degradation in algorithms like t-SNE, Spectral Clustering, and spatial indexing.

The Isolation Kernel (IK) Mechanism

Instead of calculating a closed-form geometric distance, the Isolation Kernel (IK) derives similarity directly from the dataset using a space partitioning mechanism. The algorithm creates multiple random partitionings of the data space to isolate points. Similarity between two points is defined as the probability (or expectation) that they fall into the same isolating partition.

Crucially, the probability of a point falling into an IK partition is independent of the data distribution and the dimensionality of the space. This allows IK to maintain distinguishability even as dimensions approach infinity, unlike standard kernels which inevitably suffer from the concentration effect.

Empirical Evidence of Stability

The authors evaluated IK against Gaussian (GK) and Linear (LK) kernels using both real-world (e.g., MNIST, CIFAR-10) and synthetic datasets. A key metric used is $N_\epsilon$, which represents the number of points within a small distance $\epsilon$ of a query point. In a stable search, $N_\epsilon$ should remain small and consistent.

Figure 1: (a) Synthetic dataset used. (b) Concentration effect: variance of kernel values for IK vs GK. (c-d) Stability of nearest neighbors ($N_\epsilon$) for query points $q_i$ (between clusters) and $q_c$ (cluster center) as dimensions ($d$) increase.

As shown in Figure 1, while GK and LK exhibit severe query instability—with $N_\epsilon$ exploding as dimensions scale from 10 to 10,000—IK maintains a constant, stable distinguishability score. This stability is a direct result of IK's data-dependent partitioning, which avoids the concentration of measure seen in distance-based metrics.

Comparative Performance

IK was also compared against other methods designed for high-dimensional robustness, such as Shared Nearest Neighbors (SNN) and Adaptive Gaussian (AG) kernels.

Figure 2: Comparison of IK with SNN and AG kernels. IK maintains $N_\epsilon \approx 1$ across all dimensions, while SNN and AG struggle to maintain stability in very high dimensions.

Impact on Machine Learning Tasks

The theoretical advantages of IK translate into significant practical gains across various domains:

  • Faster Indexing: Using IK enabled ball tree indexing to run faster than brute-force search across all tested datasets, including those with over 40,000 dimensions, where traditional spatial indexing typically fails.
  • Superior Clustering: IK significantly outperformed Gaussian and Adaptive Gaussian kernels in Spectral and Density-Peak clustering, particularly on complex synthetic datasets like $w$-Gaussians.
  • Classification Efficiency: SVMs using IK matched or exceeded the accuracy of Linear and Gaussian kernels while allowing for fast linear solvers, resulting in speedups of up to two orders of magnitude.
  • Accurate Visualization: t-SNE with IK successfully preserved data structures in high dimensions where standard t-SNE (using Gaussian kernels) collapsed clusters into indistinguishable blobs.

Conclusion

This work provides both theoretical and empirical proof that the Isolation Kernel can break the curse of dimensionality. By moving away from metric-based distances to data-dependent space partitioning, IK enables robust performance in high-dimensional spaces. Future work includes exploring whether other isolation mechanisms, like Isolation Forests, offer similar formal guarantees and investigating IK's resistance to the "hubness" effect.

Summary updated

Abstract

The curse of dimensionality has been studied in different aspects. However, breaking the curse has been elusive. We show for the first time that it is possible to break the curse using the recently introduced Isolation Kernel. We show that only Isolation Kernel performs consistently well in indexed search, spectral & density peaks clustering, SVM classification and t-SNE visualization in both low and high dimensions, compared with distance, Gaussian and linear kernels. This is also supported by our theoretical analyses that Isolation Kernel is the only kernel that has the provable ability to break the curse, compared with existing metric-based Lipschitz continuous kernels.
BibTeX
@misc{ting2021breaking,
  author = {Kai Ming Ting and Takashi Washio and Ye Zhu and Yang Xu},
  title = {{Breaking the curse of dimensionality with Isolation Kernel}},
  year = {2021},
  eprint = {2109.14198},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.14198},
}
Figure