Research map / Probabilistic and scientific modeling / Molecules and proteins

Partition First, Embed Later: Laplacian-Based Feature Partitioning for Refined Embedding and Visualization of High-Dimensional Data

ICML 2025 · Probabilistic and scientific modeling › Molecules and proteins · approach: Sparse graphical and tensor models

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes partitioning high-dimensional features into K mutually exclusive subsets via a graph-Laplacian smoothness objective, then building a separate similarity graph and embedding per subset, with theory on recovering the true partitions.

Problem

Standard embedding and visualization methods (tSNE, UMAP, Laplacian Eigenmaps, Diffusion Maps) build one graph from all features, which can distort or obscure structure when data is governed by several distinct latent variables that live in different feature subsets.

Approach

Jointly learn a partition of features and a row-normalized Gaussian affinity graph per partition by minimizing the sum of graph smoothness scores; each feature is assigned to the partition in which it is smoothest. Theory shows the minimizer recovers the correct partition under partially dependent manifold models in a high-dimensional asymptotic regime.

Key results

• On the independent and partially dependent ellipsoid datasets, the proposed feature partitioning recovers the correct partition with 0 average coordinate errors, while k-means, spectral clustering, bi-clustering and co-clustering incur about 1.7 to 2.2 errors out of 6.
• On dermal scRNA-seq data, the feature partition based embeddings yield the lowest k-NN error against both cell type development and cell cycle latent variables, outperforming tSNE on all features, IC-PML, LDLE and Multi-tSNE.
• Theorem 4.4 shows that for K=2 the limiting minimizer of the asymptotic objective is a trivial partition (0,1) or (1,0) that aligns with the true feature partition as bandwidth tends to zero.

Measured effects reported in the paper

Surprising findings

• Traditional clustering and bi-clustering methods perform poorly at partitioning features even on simple simulated data with independent subsets.

Limitations

• Number of partitions K must be specified in advance; automatic selection is left for future work.
• Theory covers a variant of the objective in a high-dimensional asymptotic regime and K=2 for the minimizer result.
• Alternating minimization is sensitive to local minima; a regularized annealing procedure is used to mitigate this.

Experimental setup

Datasets: Dermal scRNA-seq (Qu et al., 2024), N=5572, D=5000 Liver scRNA-seq (Droin et al., 2021), N=6889, D=2000 Simulated product of 2D ellipsoids in R6 (N=1000) COIL-20 subset

Benchmarks: Product of 2D ellipsoids partitioning error Dermal scRNA-seq k-NN error vs latent variables Liver scRNA-seq qualitative embedding

Metrics: partitioning error (number of misassigned coordinates) k-nearest neighbor error

Baselines: tSNE on all features IC-PML LDLE Multi-tSNE k-means on features spectral clustering on features bi-clustering co-clustering

Builds on: tSNE Laplacian Eigenmaps Diffusion Maps Laplacian score Multi-tSNE

Closest papers by meaning

• Finsler Multi-Dimensional Scaling: Manifold Learning for Asymmetric Dimensionality Reduction and Embedding (CVPR 2025 · similarity 0.87)
• Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction (CVPR 2022 · similarity 0.87)
• Learning Mixed-Curvature Representations in Product Spaces (ICLR 2019 · similarity 0.87)
• Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.86)
• How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.86)
• Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.85)