NEST: Nested Embedding Representation for Multiscale Clustering

Zhanqi Zhang; Mikio Aoi; Gal Mishne

cs.LGOct 21, 2026

NEST: Nested Embedding Representation for Multiscale Clustering

Authors: Zhanqi Zhang, Mikio Aoi, Gal Mishne

Organizations: Computer Science and Engineering, UC San Diego · Halıcıoğlu Data Science Institute, UC San Diego · Neurobiology, UC San Diego · Electrical and Computer Engineering, UC San Diego

Abstract

Real-world data often exhibits cluster structure at multiple resolutions, yet existing methods typically learn a single partition or construct an explicit hierarchy. Inspired by Matryoshka Representation Learning, we introduce NEST, an unsupervised framework that encodes coarse-to-fine structure within a single embedding. NEST jointly optimizes clustering and separation across nested prefix subspaces, enabling progressively finer distinctions as embedding dimensionality increases, with rank and within-cluster regularization that keep the embedding from collapsing. Empirically, distances in the learned embedding follow the hierarchy distance more closely than those of the input, although the hierarchy is never observed during training. On synthetic hierarchies, NEST recovers multiscale structure given only the number of clusters per level. Experiments on vision, text, and single-cell data further demonstrate multiscale organization across real-world representations. By making clustering granularity an intrinsic property of the representation, NEST provides a unified approach to multiscale structure discovery.

Figures & tables

Figure 1: NEST. (a) Fine clusters

\mathcal{C}_{3}

nest inside

\mathcal{C}_{2}

and

\mathcal{C}_{1}

; the prefix

z_{1:m_{\ell}}

resolves level

\ell

, with longer prefixes supporting progressively finer clustering. (b) A trainable map

f_{\theta}

adapts frozen features

h_{i}=g(x_{i})

through a residual correction. Each prefix is optimized with a level-specific clustering and separation objective (

\mathcal{L}^{(\ell)}_{\mathrm{DEC}}+\mathcal{L}^{(\ell)}_{\mathrm{sep}}

), while the rank and within-cluster regularizers

\mathcal{L}_{\mathrm{rank}}

and

\mathcal{L}_{\mathrm{within}}

keep the embedding from collapsing.

		NMI				ARI				ACC
Dataset	$K$	$k$ -means	Ward	HDB	NEST	$k$ -means	Ward	HDB	NEST	$k$ -means	Ward	HDB	NEST
Nested GMM	$4$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$
	$16$	$\underline{.99}{\scriptstyle\pm.01}$	$\underline{.99}{\scriptstyle\pm.00}$	$.67{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$.95{\scriptstyle\pm.04}$	$\underline{.99}{\scriptstyle\pm.00}$	$.33{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$	$.94{\scriptstyle\pm.05}$	$\underline{.99}{\scriptstyle\pm.00}$	$.25{\scriptstyle\pm.00}$	$\mathbf{1.00}{\scriptstyle\pm.00}$
	$64$	$\underline{.67}{\scriptstyle\pm.00}$	$\underline{.67}{\scriptstyle\pm.00}$	$.50{\scriptstyle\pm.00}$	$\mathbf{.82}{\scriptstyle\pm.01}$	$\underline{.25}{\scriptstyle\pm.00}$	$\underline{.25}{\scriptstyle\pm.00}$	$.09{\scriptstyle\pm.00}$	$\mathbf{.41}{\scriptstyle\pm.02}$	$\underline{.28}{\scriptstyle\pm.00}$	$\underline{.28}{\scriptstyle\pm.00}$	$.06{\scriptstyle\pm.00}$	$\mathbf{.29}{\scriptstyle\pm.04}$
Balanced tree	$3$	$\underline{.75}{\scriptstyle\pm.01}$	$.73{\scriptstyle\pm.01}$	$.00{\scriptstyle\pm.00}$	$\mathbf{.76}{\scriptstyle\pm.01}$	$\underline{.71}{\scriptstyle\pm.01}$	$.70{\scriptstyle\pm.01}$	$.00{\scriptstyle\pm.00}$	$\mathbf{.72}{\scriptstyle\pm.02}$	$\underline{.74}{\scriptstyle\pm.01}$	$.73{\scriptstyle\pm.01}$	$.48{\scriptstyle\pm.00}$	$\mathbf{.75}{\scriptstyle\pm.02}$
	$7$	$\underline{.79}{\scriptstyle\pm.07}$	$.67{\scriptstyle\pm.06}$	$.05{\scriptstyle\pm.07}$	$\mathbf{.95}{\scriptstyle\pm.08}$	$\underline{.72}{\scriptstyle\pm.10}$	$.64{\scriptstyle\pm.06}$	$.00{\scriptstyle\pm.01}$	$\mathbf{.94}{\scriptstyle\pm.12}$	$\underline{.71}{\scriptstyle\pm.07}$	$.70{\scriptstyle\pm.04}$	$.25{\scriptstyle\pm.03}$	$\mathbf{.94}{\scriptstyle\pm.11}$

Table 1: Clustering on synthetic data. Mean

\pm

s.d. over 5 seeds, with each seed drawing a new dataset. Best in bold and second best underlined.

	$K=20$			$K=100$
CIFAR-100	NMI	ARI	ACC	NMI	ARI	ACC
k-means	.33±.00	.10±.01	.30±.01	.48±.00	.10±.00	.28 ±.00
Ward	.33	.08	.28	.47	.09	.27
Avg-L (Euc)	.02	.00	.06	.13	.00	.06
HypHC	.07±.02	.02±.01	.10±.01	.23±.01	.01±.00	.06±.00
Bisect. k-means	.27±.00	.10±.00	.24±.00	.44±.00	.09±.00	.22±.00

Table 2: Clustering on real data. Randomized methods and NEST report mean±s.d. over the same

3

seeds; Ward and Avg-L are deterministic. Best in bold, second best underlined.

Figure 2: Clustering quality and structure. (a) CIFAR-100 vehicles 2. Left: t-SNE of the coarse prefix $z_{1:64}$ at initialization (top) and after training (bottom), with the superclass highlighted in gold. Right: t-SNE of the superclass’s image examples in the full embedding $z_{1:512}$ , colored by class. All panels: same t-SNE settings and seed. (b) Mean clustering accuracy versus cross-level consistency. (c) Training compute versus memory.

CIFAR-100, $K{=}20$
Variant	ACC	NMI
NEST	$\mathbf{.42}_{\pm.01}$	$\mathbf{.43}_{\pm.01}$
$-\mathcal{L}_{\mathrm{sep}}$	$.38_{\pm.01}$	$.39_{\pm.00}$
$-\mathcal{L}_{\mathrm{DEC}}$	$.28_{\pm.01}$	$.30_{\pm.01}$
$-\mathcal{L}_{\mathrm{rank}}$	$.28_{\pm.05}$	$.36_{\pm.05}$
$-\mathcal{L}_{\mathrm{within}}$	$.41_{\pm.01}$	$\mathbf{.43}_{\pm.01}$

Table 3: Ablation. Each row removes one component. Metrics mean

\pm

s.d. over

3

seeds.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

		NEST, joint			NEST, one level			DEC, one level
Dataset	$K$	ACC	ARI	NMI	ACC	ARI	NMI	ACC	ARI	NMI
CIFAR-100	$20$	.42 ±.01	.24 ±.01	.43 ±.01	.38±.02	.20±.02	.38±.01	.34±.01	.17±.00	.39±.00
CIFAR-100	$100$	.35±.01	.22 ±.00	.56 ±.00	.36 ±.01	.22 ±.01	.55±.01	.27±.01	.11±.01	.51±.00
20 Newsgroups	$6$	.68 ±.01	.44 ±.02	.47 ±.02	.51±.00	.30±.00	.40±.00	.57±.05	.38±.01	.40±.01
20 Newsgroups	$20$	.57 ±.02	.41 ±.01	.54 ±.01	.56±.02	.40±.02	.54 ±.01	.52±.01	.35±.00	.51±.01
Tasic 2018	$4$	.77 ±.00	.79 ±.00	.83 ±.00	.72±.01	.62±.01	.61±.01	.76±.02	.76±.06	.79±.06

Appendix

Table 4: Joint versus single-level training. ACC / ARI / NMI per level, mean

\pm

s.d. over

3

seeds, all points scored. Bold is the best of the three after rounding, ties share it.

Input
	CIFAR-100	Tasic 2018	20 Newsgroups	Balanced tree	Nested GMM	Random-branching
Representation	SCAN SimCLR	PCA	MiniLM	raw	raw	raw
Preprocessing	standardized	raw	standardized	–	–	–
$D$	$512$	$50$	$384$	$70$	$149$	$70$
$K_{\ell}$	$20/100$	$4/23/133$	$6/20$	$3/7/15$	$4/16/64$	$4/13/52$
Model

Appendix

Table 5: Hyperparameters of NEST

Figure 3: Sensitivity analysis of NEST. Accuracy of NEST minus that of the best baseline per level, varying one setting at a time; mean

\pm

s.d. over

3

(real) or

5

(synthetic) seeds. Columns:

\lambda_{\mathrm{rank}}

with

\lambda_{\mathrm{within}}

fixed;

\lambda_{\mathrm{within}}

with

\lambda_{\mathrm{rank}}

fixed; coarse prefix width

m_{1}

; level weights (real data: coarse weight

a_{1}

, others

1

; synthetic:

a_{\ell}=r^{\ell-1}

with the regularization weights fixed). Dashed line: reported configuration.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 342 papers

CAESAR: Clustering via Autonomous Embedding-Space Agglomerative Reorganization
Sep 26, 2026Ilan Bacry, Rémi Devaux, Antoine JardinCluster Number Estimation Clustering
Arlequin AI
Polaris: Coupled Orbital Polar Embeddings for Hierarchical Concept Learning
Apr 30, 2026Sahil Mishra, Srinitish Srinivasan, Sourish Dasgupta +1Hierarchical Classification Hierarchical Representation Learning
Indian Institute of Technology Delhi, New Delhi, India · KDM Lab, Dhirubhai Ambani University, Gandhinagar, Gujarat, India · Indian Institute of Technology Delhi, Abu Dhabi, UAE.
The elbow statistic: Multiscale clustering statistical significance
Mar 3, 2026Francisco J. Perez-RecheCluster Number Estimation Clustering
School of Natural and Computing Sciences, University of Aberdeen, Fraser Noble Building, AB24 3UE, United Kingdom

Sep 26, 2026J/K move · Enter open · S save

CAESAR: Clustering via Autonomous Embedding-Space Agglomerative Reorganization

Ilan Bacry, Rémi Devaux, Antoine Jardin

Arlequin AI

Cluster Number Estimation Clustering Unsupervised Clustering Deep Clustering Image Clustering

Open paper AskPDF arXiv

Clustering algorithms that operate on nearest-neighbor graphs, such as FINCH (First Integer Neighbor Clustering Hierarchy), depend heavily on the quality of the embedding space they are given. However, pretrained vision and language model embeddings are not optimized for this purpose. We propose CAESAR, a method that reorganizes a pretrained embedding space: a reorganization network is trained to pull mutual nearest neighbors together and push non-neighbors apart, yielding a reorganized embedding space substantially better suited to clustering. CAESAR offers a second major advantage: it never requires the number of clusters

K

. This matters because in realistic unsupervised settings,

K

is typically unknown and discovering it is often part of the problem, yet most strong clustering methods take it as an input. We therefore design the entire CAESAR pipeline to infer

K

rather than assume it is known. Empirically, reorganizing the embeddings consistently improves clustering over the raw space on both text and image datasets. Since the few deep clustering methods that also infer

K

do not release their code, we complement controlled comparisons with methods that infer

K

on the same embedding space by comparisons with strong deep clustering methods that are given the true

K

, giving them a substantial oracle advantage. Even so, CAESAR outperforms all of them on text, achieves the best results on the most challenging image benchmark and remains competitive on the others. Reorganizing pretrained embeddings thus emerges as a simple and powerful route to clustering realistic data, where classes overlap and the number of clusters is unknown.

Abstract

Clustering

Explore similar work

CAESAR: Clustering via Autonomous Embedding-Space Agglomerative Reorganization

Polaris: Coupled Orbital Polar Embeddings for Hierarchical Concept Learning

The elbow statistic: Multiscale clustering statistical significance