Laplacian-based Cluster-Contractive t-SNE for High-Dimensional Data Visualization

t-SNE на основе лапласиана со стягиванием кластеров для визуализации многомерных данных
Jicong Fan, Yan Sun, Yi Han
2023-08-03

Laplacian-based t-SNEgraph Laplacianhigh-dimensional data visualizationmajorization-minimization algorithmnonlinear dimensionality reduction
Dimensionality reduction techniques aim at representing high-dimensional data in low-dimensional spaces to extract hidden and useful information or facilitate visual understanding and interpretation of the data. However, few of them take into consideration the potential cluster information contained implicitly in the high-dimensional data. In this article, we propose Lap tSNE, a new graph-layout nonlinear dimensionality reduction method based on t-SNE, one of the best techniques for visualizing high-dimensional data as 2D scatter plots. Specifically, Lap tSNE leverages the eigenvalue information of the graph Laplacian to shrink the potential clusters in the low-dimensional embedding when learning to preserve the local and global structure from high-dimensional space to low-dimensional space. It is nontrivial to solve the proposed model because the eigenvalues of normalized symmetric Laplacian are functions of the decision variable. We provide a majorization-minimization algorithm with convergence guarantee to solve the optimization problem of Lap tSNE and show how to calculate the gradient analytically, which may be of broad interest when considering optimization with Laplacian-composited objective. We evaluate our method by a formal comparison with state-of-the-art methods on seven benchmark datasets, both visually and via established quantitative measurements. The results demonstrate the superiority of our method over baselines such as t-SNE and UMAP. We also provide out-of-sample extension, large-scale extension, and mini-batch extension for our Lap tSNE to facilitate dimensionality reduction in various scenarios.
1
Across seven benchmark datasets, Lap tSNE outperforms state-of-the-art baselines, including t-SNE and UMAP, in visual and established quantitative evaluations.
2
Because normalized symmetric Laplacian eigenvalues depend on the optimization variables, the authors develop a majorization-minimization algorithm with a convergence guarantee and an analytical gradient.
3
Lap tSNE is a graph-layout nonlinear dimensionality reduction method that extends t-SNE by exploiting graph Laplacian eigenvalue information to contract implicit clusters in low-dimensional embeddings.
4
The framework includes out-of-sample, large-scale, and mini-batch extensions for broader dimensionality-reduction applications.
5
The method jointly preserves local and global high-dimensional structure while shrinking potential clusters to improve two-dimensional visualization.

high-dimensional data represented in low-dimensional embeddings

preservation of local and global structure with cluster contraction in the low-dimensional embedding for visualization

Publication Details
Publication Date
2023-08-03
Journal
Publisher
ISSN
Cited by
11
Access Type
Author Information
Authors
Jicong Fan
Yan Sun
Yi Han
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%