betaFeedback

WorksComputer Science

NEST: Nested Embedding Representation for Multiscale Clustering

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.

Introduction

Clustering is a fundamental tool for unsupervised structure discovery, yet real-world data often admits meaningful organization at multiple levels of resolution. Images, for example, may separate into broad semantic groups such as animals and vehicles, and further into individual object categories. Likewise, biological populations can be organized into broad cell classes, subclasses, and increasingly specialized cell types. A useful representation should therefore support structure discovery across several resolutions, rather than only a single partition.

Classical clustering methods typically operate directly on a fixed feature space. Flat methods such as kk-means ([8]) recover a partition at a specified resolution, while hierarchical methods recover nested partitions across multiple resolutions, either agglomeratively or divisively ([23, 18]). Other approaches, such as spectral or hyperbolic embedding methods ([15, 16]), first transform the data into a representation in which cluster structure is then identified. Across these settings, clustering quality depends on how well the representation preserves the distinctions required at each resolution. Clustering with deep learning ([25, 26, 3]) addresses the representation problem by jointly learning embeddings and cluster assignments, but is typically optimized for a single clustering resolution. Thus, hierarchical clustering provides multiscale structure without representation learning, while deep clustering provides representation learning without explicitly organizing multiple resolutions.

We ask whether these two capabilities can be learned jointly, such that a single representation captures cluster structure at both coarse and fine resolutions simultaneously. Inspired by Matryoshka Representation Learning ([11]), we introduce Nested Embedding RepreSentation for MulTiscale Clustering (NEST). NEST learns a single embedding whose nested prefixes are jointly optimized for progressively finer cluster structure. Unlike conventional MRL, where prefixes of different lengths are trained for the same downstream objective, for example, the same classification or retrieval task at different embedding sizes, NEST assigns each prefix a different clustering resolution. Shorter prefixes capture coarser structure, while longer prefixes capture progressively finer structure.

By encoding clustering resolution directly in the representation, NEST can learn multiscale cluster structure without access to a ground-truth hierarchy or explicit construction of a cluster tree during training. Instead, coarse-to-fine organization is learned through the nested subspaces themselves. We show empirically that distances in the learned embedding correlate more strongly with the hierarchy distance than those of the input, connecting the learned representation to hierarchical geometry. We validate NEST on synthetic, visual, text, and single-cell data, where it recovers coarse-to-fine cluster structure given only the number of clusters at each resolution. Together, these results introduce a simple representation-based approach to multiscale clustering and demonstrate that hierarchical organization can emerge from nested subspaces without explicitly learning a tree.

Related Work

Hierarchical Clustering organizes data into nested tree structures through bottom-up merging or top-down splitting [23, 18]. Beyond such procedural constructions, Dasgupta [5] formulated hierarchical clustering as optimization of a global tree objective over pairwise similarities. Hyperbolic representation learning provides a complementary route for modeling tree-like structure, exploiting the geometry of hyperbolic space to embed hierarchical relations [16]. Chami et al. [4] connect these ideas by using hyperbolic embeddings to obtain a differentiable relaxation of Dasgupta’s objective and recover a hierarchy from the learned geometry.

More recent deep-learning-based hierarchical clustering methods couple representation learning with explicit tree construction. For example, Mautz et al. [14] jointly learn an autoencoder representation and a binary tree that expands through recursive splits, while Znaleźniak et al. [27] use contrastive learning to recover hierarchical cluster structure. In contrast to methods that represent hierarchy through explicit tree structures or hierarchical objectives, NEST encodes multiscale cluster structure directly in the representation, with nested embedding prefixes specialized to different resolutions.

Representation Learning for Clustering. Learning feature representations has significantly improved clustering performance by producing embeddings that better separate semantic groups. Classical deep clustering approaches include [25, 26, 3], which learn cluster structures jointly with representation learning. Huang et al. [9] maximize global partition confidence using a Partition Uncertainty Index to jointly optimize cluster separability and compactness. Wu et al. [24] mine multi-level correlations between samples using pseudo-graphs and pseudo-labels to guide representation learning. Li et al. [13] jointly perform instance-level and cluster-level contrastive learning by treating feature rows as soft assignments and columns as cluster prototypes. Unlike these methods, which aim to learn a single clustering partition, our approach focuses on representations that support multiple clustering resolutions.

Matryoshka Representation Learning was introduced by Kusupati et al. [11], who trained nested prefixes of an embedding to remain useful at different dimensionalities. Bhalgat et al. [1] learn a nested representation for 3D scene understanding, but their coarse-to-fine structure is explicitly provided during training. Hanley and Durumeric [7] train multilingual Matryoshka embeddings using labeled pairs of news articles with graded semantic similarity, applying a contrastive loss at different prefix lengths so that the prefixes encode progressively finer notions of news similarity. They then apply a separate hierarchical clustering algorithm to the learned embeddings. FRANCA (Venkataramanan et al. [21]) is close to our setting in that it also uses nested prefixes with progressively finer prototype assignments. However, FRANCA uses these assignments to learn visual representations, whereas NEST treats the clusterings themselves as the target output, directly optimizing multiscale clustering on a fixed input representation.

Nested Clustering

We formulate multiscale clustering as learning a single nested representation that supports clustering at multiple resolutions. NEST uses a Matryoshka-style embedding in which progressively longer prefixes encode increasingly fine structure (Figure 1a).

Figure 1. NEST. (a) Fine clusters C3\mathcal{C}_3 nest inside C2\mathcal{C}_2 and C1\mathcal{C}_1; the prefix z1:mℓz_{1:m_\ell} resolves level ℓ\ell, with longer prefixes supporting progressively finer clustering. (b) A trainable map fθf_\theta adapts frozen features hi=g(xi)h_i = g(x_i) through a residual correction. Each prefix is optimized with a level-specific clustering and separation objective (LDEC(ℓ)+Lsep(ℓ))(\mathcal{L}_{\mathrm{DEC}}^{(\ell)}+\mathcal{L}_{\mathrm{sep}}^{(\ell)}), while the rank and within-cluster regularizers Lrank\mathcal{L}_{\mathrm{rank}} and Lwithin\mathcal{L}_{\mathrm{within}} keep the embedding from collapsing.

Problem setup. Let D={xi}i=1ND = \{x_i\}_{i=1}^{N} be an unlabeled dataset, and LL denote the number of clustering resolutions. For each level ℓ∈{1,…,L}\ell\in\{1, \ldots, L\}, we specify a target number of clusters KℓK_\ell, ordered from coarse to fine,

K1<K2<⋯<KL.K_1 < K_2 < \cdots< K_L.

We denote the clustering induced at level ℓ\ell by

Cℓ={Cℓ,1,…,Cℓ,Kℓ}.C_\ell= \{C_{\ell,1}, \ldots, C_{\ell,K_\ell}\}.

Given these resolutions, the only multiscale information supplied to NEST is the target cluster count KℓK_\ell at each resolution; no parent-child assignments, tree structure, or ground-truth hierarchy are used during training.

Nested representation. Each sample is first mapped by a frozen feature extractor gg (e.g., a pretrained encoder, or a fixed projection such as PCA) to features hi=g(xi)∈RDh_i = g(x_i) \in\mathbb{R}^{D}. NEST learns a residual map on these features,

zi=Ohi+γfθ(hi)∈RD,(1)z_i = O h_i + \gamma f_\theta(h_i) \in\mathbb{R}^{D}, \tag*{(1)}

where fθf_\theta is a trainable MLP (Figure 1b) and γ>0\gamma> 0 sets the scale of the learned correction. OO is a fixed orthogonal D×DD \times D matrix, so NEST keeps the encoder’s width. The MLP’s last layer is initialized to zero so at initialization, zi=Ohiz_i = O h_i has identical pairwise distances of the input. On the real datasets OO rotates hih_i into its principal axes, computed once from the features, ordering the coordinates by variance so that each prefix starts from the leading directions. On the synthetic data O=IO = I (Appendix § 16).

We choose nested prefix dimensions m1<⋯<mL=Dm_1 < \cdots< m_L = D, and define the representation used at level ℓ\ell as

zi(ℓ):=zi;mℓ∈Rmℓ.z_i^{(\ell)} := z_{i; m_\ell} \in\mathbb{R}^{m_\ell}.

Thus, coarse clustering operates on a shorter prefix, while finer levels retain the coarse coordinates and progressively add further coordinates.

Level-wise clustering. For each level ℓ\ell, NEST learns KℓK_\ell trainable cluster centers

{μk(ℓ)}k=1Kℓ,μk(ℓ)∈Rmℓ.\left\{\mu_k^{(\ell)}\right\}_{k=1}^{K_\ell}, \qquad\mu_k^{(\ell)} \in\mathbb{R}^{m_\ell}.

Each center represents one cluster at that resolution. A point is assigned to a cluster based on its distance to these centers in the corresponding prefix space. At each resolution, NEST applies the Deep Embedded Clustering (DEC) objective (Xie et al. [25]) to the corresponding prefix representation.

For sample ii and center kk at level ℓ\ell, we compute the Euclidean distance between the level-specific prefix zi(ℓ)z_i^{(\ell)} and cluster center μk(ℓ)\mu_k^{(\ell)}, scaled per level by αℓ/s^ℓ\alpha_\ell/ \hat{s}_\ell, where αℓ>0\alpha_\ell> 0 is the level weight and s^ℓ\hat{s}_\ell the initial center spacing (both defined below):

δik(ℓ)=αℓs^ℓ∥zi(ℓ)−μk(ℓ)∥2,(2)\delta_{ik}^{(\ell)} = \frac{\alpha_\ell}{\hat{s}_\ell} \left\lVert z_i^{(\ell)} - \mu_k^{(\ell)} \right\rVert_2, \tag*{(2)}

These rescaled distances measure how far sample ii is from cluster kk at resolution ℓ\ell.

Following DEC (Xie et al. [25]), we convert these distances into Student-tt soft assignments over the KℓK_\ell clusters, by assigning a nonnegative weight qik(ℓ)q_{ik}^{(\ell)} to cluster kk, with larger weights for centers closer to zi(ℓ)z_i^{(\ell)}

qik(ℓ)=(1+(δik(ℓ))2)−1∑j=1Kℓ(1+(δij(ℓ))2)−1.(3)q_{ik}^{(\ell)} = \frac{\left(1 + \left(\delta_{ik}^{(\ell)}\right)^2\right)^{-1}} {\sum_{j=1}^{K_\ell} \left(1 + \left(\delta_{ij}^{(\ell)}\right)^2\right)^{-1}}. \tag*{(3)}

To give more weight to confident assignments while preventing large clusters from dominating the target distribution, the soft assignments are sharpened and reweighted by cluster frequency. Let

fk(ℓ)=∑iqik(ℓ),f_k^{(\ell)} = \sum_i q_{ik}^{(\ell)},

where fk(ℓ)f_k^{(\ell)} is the total soft-assignment mass of cluster kk. The sharpened target distribution is

pik(ℓ)=(qik(ℓ))2/fk(ℓ)∑j=1Kℓ(qij(ℓ))2/fj(ℓ).(4)p_{ik}^{(\ell)} = \frac{\left(q_{ik}^{(\ell)}\right)^2 / f_k^{(\ell)}}{\sum_{j=1}^{K_\ell}\left(q_{ij}^{(\ell)}\right)^2 / f_j^{(\ell)}} . \tag*{(4)}

where P(ℓ)P^{(\ell)} is computed from the current assignments but treated as a fixed target during optimization. Gradients are not propagated through P(ℓ)P^{(\ell)}.

The clustering objective at level ℓ\ell is then the KL divergence between the sharpened target distribution P(ℓ)P^{(\ell)} and the current soft assignments Q(ℓ)Q^{(\ell)}:

LDEC(ℓ)=KL⁡(P(ℓ)∥Q(ℓ)).(5)\mathcal{L}_{\mathrm{DEC}}^{(\ell)} = \operatorname{KL}\left(P^{(\ell)} \parallel Q^{(\ell)}\right). \tag*{(5)}

Center-separation penalty. The DEC objective encourages samples to concentrate around cluster centers but does not explicitly keep different cluster centers separated. As a result, multiple centers can move toward the same location, causing different clusters to collapse onto one another.

We therefore add a separation penalty that keeps different cluster centers at least a margin ρℓ\rho_\ell apart. Specifically, at level ℓ\ell, let kk and k′k' index two different cluster centers among the KℓK_\ell centers. We define

Eℓ={(k,k′):1≤k<k′≤Kℓ}\mathcal{E}_\ell= \{(k,k') : 1 \leq k < k' \leq K_\ell\}

as the set of all unordered pairs of different cluster centers at that level. The separation loss is

Lsep(ℓ)=1∣Eℓ∣∑(k,k′)∈Eℓ[ρℓ−∥μk(ℓ)−μk′(ℓ)∥2]+,(6)\mathcal{L}_{\mathrm{sep}}^{(\ell)} = \frac{1}{\lvert\mathcal{E}_\ell\rvert}\sum_{(k,k')\in\mathcal{E}_\ell}\left[\rho_\ell-\left\lVert\mu_k^{(\ell)}-\mu_{k'}^{(\ell)}\right\rVert_2\right]_+ , \tag*{(6)}

where ρℓ\rho_\ell is the required minimum separation between centers at level ℓ\ell, and [u]+=max⁡(u,0)[u]_+ = \max(u,0) denotes the positive-part function which returns uu when u>0u > 0 and 0 otherwise.

Thus, a pair of centers is penalized only when their distance is smaller than ρℓ\rho_\ell, and centers already separated by at least ρℓ\rho_\ell receive no penalty.

Setting scale parameters. We now define the level-specific distance scale s^ℓ\hat{s}_\ell and separation margin ρℓ\rho_\ell introduced above. The cluster centers are initialized independently at each level by kk-means (n_init = 10) on the initial corresponding prefix z(ℓ)z^{(\ell)}. For the full resolution ℓ=L\ell= L, this is equivalent to kk-means in the input feature space hih_i. From this initialization, we compute two level-specific distance statistics.

First, s^ℓ\hat{s}_\ell is the minimum Euclidean distance between initialized cluster centers at level ℓ\ell, measuring the separation of the closest pair of clusters. Thus the distances used in the DEC soft assignments are normalized relative to the initial spacing between cluster centers.

Second, r^ℓ\hat{r}_\ell is the mean Euclidean distance from each sample to the center of the cluster assigned to it by the initial kk-means solution. It measures the typical initial within-cluster radius at level ℓ\ell. We use it to set the separation margin

ρℓ=4r^ℓ,\rho_\ell= 4\hat{r}_\ell,

so that two learned centers are penalized when they become closer than four times the initial within-cluster radius. The factor 4 is a heuristic taken from a worst-case argument (Appendix § 10).

Degeneracy regularization. The clustering objective can lead to two degenerate solutions: collapse onto a low-dimensional subspace, and contraction of clusters to near-point masses. These are different failures: the first is a global loss of directions, which Lrank\mathcal{L}_{\mathrm{rank}} addresses, and the second is a local contraction within clusters, which Lwithin\mathcal{L}_{\mathrm{within}} addresses.

The rank regularization discourages the representation from collapsing onto a small number of directions

Lrank=1L∑ℓ=1L[1−eℓtr⁡eℓ]+2.(7)\mathcal{L}_{\mathrm{rank}} = \frac{1}{L}\sum_{\ell=1}^{L}\left[1-\frac{e_\ell}{\operatorname{tr}e_\ell}\right]_+^2 . \tag*{(7)}

Here eℓ=erank⁡(B(ℓ))e_\ell= \operatorname{erank}(B^{(\ell)}) is the effective rank of B(ℓ)∈RN×(mℓ−mℓ−1)B^{(\ell)} \in\mathbb{R}^{N\times(m_\ell-m_{\ell-1})}, whose rows contain the coordinates introduced at level ℓ\ell, zi,mℓ−1+1:mℓz_{i,m_{\ell-1}+1:m_\ell}, with m0=0m_0=0.

erank⁡(Z)=exp⁡(−∑jpjlog⁡pj),(8)\operatorname{erank}(Z) = \exp\left(-\sum_j p_j\log p_j\right), \tag*{(8)}

where pj=σj2/∑kσk2p_j = \sigma_j^2/\sum_k \sigma_k^2 and σj\sigma_j are the singular values of the column-centered matrix ZZ. The reference eℓ0e_\ell^0 is the same quantity for the initial embedding z=Θhz = \Theta h.

The cluster spread regularization keeps clusters from contracting to near-point masses, preserving non-degenerate within-cluster variation; when applied at a coarser level, that variation is also what finer partitions are built from. At level ℓ\ell,

Lwithin=[1−w(ℓ)τww0(ℓ)]+2,(9)\mathcal{L}_{\mathrm{within}} = \left[1-\frac{w^{(\ell)}}{\tau_w w_0^{(\ell)}}\right]_+^2 , \tag*{(9)}

and the loss is averaged over the levels at which it is applied (Table 5). Here w(ℓ)w^{(\ell)} is the within-cluster spread at level ℓ\ell, the mean squared distance of a point’s prefix to the mean of its assigned cluster,

Table 5: Hyperparameters of NEST

CIFAR-100Tasic 201820 NewsgroupsBalanced treeNested GMMRandom-branching
Input
RepresentationSCANSimCLRPCAMiniLMrawrawraw
Preprocessingstandardizedrawstandardized–––
DD512503847014970
KℓK_{\ell}20/1004/23/1336/203/7/154/16/644/13/52
Model
Coordinates (basis OO)principal axesprincipal axes (released PCA)principal axesnativenativenative
Prefix widths mℓm_{\ell}64/5126/25/5032/3848/35/7018/74/1498/35/70
Residual scale γ\gamma0.10.10.10.30.30.3
Objective
Level weights aℓa_{\ell}0.5:10.5:1:10.5:11:1:11:2:41:1:1
λrank\lambda_{\mathrm{rank}}10100.30.14.30.1
τr\tau_r (rank fraction)0.750.750.750.750.750.75
λwithin\lambda_{\mathrm{within}}1010100.14.30.1
τw\tau_w (within fraction)0.750.750.750.750.750.75
Levels where Lwithin\mathcal{L}_{\mathrm{within}} actsfinestfinestfinestallfinestall

Table 5.

w(ℓ)=1N∑i=1N∥zi(ℓ)−zˉci(ℓ)∥2.(10)w^{(\ell)} = \frac{1}{N}\sum_{i=1}^{N}\left\lVert z_i^{(\ell)}-\bar{z}_{c_i}^{(\ell)}\right\rVert^2 . \tag*{(10)}

where ci=arg⁡min⁡kδik(ℓ)c_i = \arg\min_k \delta_{ik}^{(\ell)} is the cluster assigned to point ii, zˉk(ℓ)\bar{z}_k^{(\ell)} is the mean of zi(ℓ)z_i^{(\ell)} over the points assigned to cluster kk, and w0(ℓ)w_0^{(\ell)} is the same quantity at initialization.

The activation fractions τr\tau_r and τw\tau_w determine when each soft penalty begins to increase. Otherwise the terms remain zero, allowing the embedding to move freely away from hh.

NEST objective. All levels are optimized jointly with

∑ℓ=1Laˉℓ(LDEC(ℓ)+Lsep(ℓ))+λrankLrank+λwithinLwithin.(11)\sum_{\ell=1}^{L} \bar{a}_{\ell}\left(\mathcal{L}_{\mathrm{DEC}}^{(\ell)}+\mathcal{L}_{\mathrm{sep}}^{(\ell)}\right)+\lambda_{\mathrm{rank}}\mathcal{L}_{\mathrm{rank}}+\lambda_{\mathrm{within}}\mathcal{L}_{\mathrm{within}}. \tag*{(11)}

Here aˉℓ=aℓ/(1L∑kak)\bar{a}_{\ell}=a_{\ell}/\left(\frac{1}{L}\sum_k a_k\right) is the level weight of (2) normalized to mean 1, so the same aℓa_{\ell} balances the resolutions in the distance and in the objective, and λrank\lambda_{\mathrm{rank}} and λwithin\lambda_{\mathrm{within}} weight the two regularizers.

Experiments

We evaluate NEST on three synthetic and three real datasets. Each dataset provides nested labels, with the number of clusters at level ℓ\ell set to the number of classes at that level K=(K1,…,KL)K=(K_1,\ldots,K_L). NEST is trained without label supervision and compared against six baselines on the real datasets and three on the synthetic datasets, using clustering metrics at every level. Across datasets, we keep most architectural and optimization settings fixed. The complete settings are reported in Table 5, with sensitivity to these choices evaluated in Appendix § 17.

Datasets

Synthetic datasets were generated with known trees. The nested GMM is a three-level Gaussian mixture, K=(4,16,64)K=(4,16,64), in which each cluster of one level splits into four at the next. The balanced tree, K=(3,7,15)K=(3,7,15), places cluster centers by a top-down walk on a balanced binary tree, so that Euclidean distance between centers tracks tree distance. The random-branching tree, K=(4,13,52)K=(4,13,52), does the same on a tree with a random number of children per node, giving coarse classes of very unequal size.

For all three datasets, level-specific hierarchical signals are first placed in separate coordinate blocks and orthogonalized. The resulting signal vector is then rotated by a fixed random orthonormal matrix, after which independent nuisance dimensions are appended. Generator parameters are in Appendix § 9.

CIFAR-100. We use the frozen 512-dimensional SimCLR ResNet-18 features from 5,000 sampled images (50 per class) released with SCAN, standardized per dimension with two levels of K=(20,100)K=(20,100).

Tasic. We use the released PCA-50 representation (i.e. O=IO=I) of 23,822 mouse cortex cells from single-cell RNA sequencing with K=(4,23,133)K=(4,23,133).

20 Newsgroups. We embed the 18,846 posts with the frozen sentence encoder all-MiniLM-L6-v2 (384 dimensions, standardized) with K=(6,20)K=(6,20).

Baselines

We compare NEST against methods from five clustering families (flat, agglomerative, divisive, hyperbolic, and deep hierarchical clustering). All baselines operate on the same frozen input representation as NEST and are evaluated at the same target cluster counts KℓK_{\ell}.

Flat clustering is represented by kk-means, run independently at each KℓK_{\ell}. Agglomerative clustering is represented by Ward and average linkage, with each construct a single dendrogram and cut it at the required resolutions. Divisive clustering is represented by bisecting kk-means, which recursively splits clusters until the target number of clusters is reached. HypHC [4] serves as the hyperbolic hierarchical baseline, and DeepECT [14] as the deep hierarchical baseline. We additionally report HDBSCAN [2] on the synthetic datasets as a density-based baseline. For NEST, each level is evaluated using its learned centers on the corresponding prefix z1:mℓz_{1:m_\ell}.

Metrics

We use three standard clustering metrics at each resolution. ACC is clustering accuracy after one-to-one matching between predicted clusters and ground-truth classes using the Hungarian algorithm [10]. ARI is the adjusted Rand index, which measures pairwise agreement corrected for chance, and NMI is normalized mutual information between predicted and ground-truth partitions.

To evaluate whether the predicted resolutions agree with one another, we also report cross-level consistency. After matching clusters to classes independently at each level, consistency is the fraction of points for which the matched fine-level class has the matched coarse-level class as its parent in the ground-truth labels. We finally compare the training compute and memory requirements of the methods using analytical estimates. Full details are in Appendix F.

Results

Synthetic hierarchical clustering

We first evaluate NEST as an unsupervised clustering method. Table 1 compares NEST with clustering directly in the observed representation.

Table 1: Clustering on synthetic data. Mean±\pms.d. over 5 seeds, with each seed drawing a new dataset. Best in bold and second best underlined.

DatasetKK\multicolumn{4}{c}{NMI}\multicolumn{4}{c}{ARI}\multicolumn{4}{c}{ACC}
Nested GMMkk-meansWardHDBNESTkk-meansWardHDBNESTkk-meansWardHDBNEST
41.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.001.00±.00\mathbf{1.00}\pm.00
16.99‾±.01\underline{.99}\pm.01.99‾±.00\underline{.99}\pm.00.67±.00.67\pm.001.00±.00\mathbf{1.00}\pm.00.95±.04.95\pm.04.99‾±.00\underline{.99}\pm.00.33±.00.33\pm.001.00±.00\mathbf{1.00}\pm.00.94±.05.94\pm.05.99‾±.00\underline{.99}\pm.00.25±.00.25\pm.001.00±.00\mathbf{1.00}\pm.00
64.67‾±.00\underline{.67}\pm.00.67‾±.00\underline{.67}\pm.00.50±.00.50\pm.00.82±.01\mathbf{.82}\pm.01.25‾±.00\underline{.25}\pm.00.25‾±.00\underline{.25}\pm.00.09±.00.09\pm.00.41±.02\mathbf{.41}\pm.02.28‾±.00\underline{.28}\pm.00.28‾±.00\underline{.28}\pm.00.06±.00.06\pm.00.29±.04\mathbf{.29}\pm.04
Balanced tree3.75‾±.01\underline{.75}\pm.01.73±.01.73\pm.01.00±.00.00\pm.00.76±.01\mathbf{.76}\pm.01.71‾±.01\underline{.71}\pm.01.70±.01.70\pm.01.00±.00.00\pm.00.72±.02\mathbf{.72}\pm.02.74‾±.01\underline{.74}\pm.01.73±.01.73\pm.01.48±.00.48\pm.00.75±.02\mathbf{.75}\pm.02
7.79±.07.79\pm.07.67±.06.67\pm.06.05±.07.05\pm.07.95±.08\mathbf{.95}\pm.08.72±.10.72\pm.10.64±.06.64\pm.06.00±.01.00\pm.01.94±.12\mathbf{.94}\pm.12.71±.07.71\pm.07.70±.04.70\pm.04.25±.03.25\pm.03.94±.11\mathbf{.94}\pm.11
15.52‾±.05\underline{.52}\pm.05.46±.05.46\pm.05.05±.05.05\pm.05.77±.02\mathbf{.77}\pm.02.26‾±.03\underline{.26}\pm.03.23±.04.23\pm.04.00±.00.00\pm.00.50±.02\mathbf{.50}\pm.02.34‾±.03\underline{.34}\pm.03.33±.03.33\pm.03.11±.01.11\pm.01.48±.03\mathbf{.48}\pm.03
Random branching4.75‾±.01\underline{.75}\pm.01.76±.01\mathbf{.76}\pm.01.00±.00.00\pm.00.60±.13.60\pm.13.52‾±.02\underline{.52}\pm.02.57±.04\mathbf{.57}\pm.04.00±.00.00\pm.00.39±.13.39\pm.13.69±.05.69\pm.05.76±.06\mathbf{.76}\pm.06.72±.00\mathbf{.72}\pm.00.63±.08.63\pm.08
13.75‾±.04\underline{.75}\pm.04.53±.02.53\pm.02.05±.07.05\pm.07.97±.02\mathbf{.97}\pm.02.62‾±.06\underline{.62}\pm.06.43±.04.43\pm.04.01±.01.01\pm.01.91±.07\mathbf{.91}\pm.07.61‾±.05\underline{.61}\pm.05.55±.05.55\pm.05.17±.03.17\pm.03.92±.06\mathbf{.92}\pm.06
52.45‾±.02\underline{.45}\pm.02.36±.01.36\pm.01.07±.03.07\pm.03.70±.02\mathbf{.70}\pm.02.13‾±.02\underline{.13}\pm.02.13‾±.01\underline{.13}\pm.01.00±.00.00\pm.00.27±.04\mathbf{.27}\pm.04.18‾±.01\underline{.18}\pm.01.16±.00.16\pm.00.05±.01.05\pm.01.25±.02\mathbf{.25}\pm.02

Table 1. Clustering on synthetic data. Mean±\pms.d. over 5 seeds, with each seed drawing a new dataset. Best in bold and second best underlined.

Across the synthetic datasets, NEST achieves the strongest overall clustering performance across resolutions, with the best results at every middle and fine resolution. Averaged across datasets, NEST improves ACC over the strongest baseline on each dataset by 0.18 at the middle resolution and by 0.07 at the fine resolution. These gains are also reflected in the permutation-invariant metrics: averaged across datasets, NEST improves NMI and ARI by 0.13 and 0.17, respectively, at the middle resolution, and by 0.22 and 0.18 at the fine resolution. At the coarse resolution, NEST matches the baselines on Nested GMM, performs best on the balanced tree, and is weaker than Ward on the random-branching tree.

Real-data hierarchical clustering

We evaluate hierarchical clustering on CIFAR-100, Tasic and 20 Newsgroups using the same frozen input representation and the same points for all methods.

Figure 2a shows the t-SNE (van der Maaten and Hinton [20]) visualization before training in the top row and after NEST training in the bottom row. The left panels plot the coarse prefix, showing how NEST reorganizes the embedding at the superclass resolution. The right panels zoom in on the vehicles 2 superclass using the full embedding, where its five constituent classes become substantially more separated after training. This illustrates how NEST keeps the coarse grouping while separating the finer classes; the quantitative evidence is in Table 2 and Figure 2b.

Table 2: Clustering on real data. Randomized methods and NEST report mean±\pms.d. over the same 3 seeds; Ward and Avg-L are deterministic. Best in bold, second best underlined.

K=20K = 20K=100K = 100
CIFAR-100NMIARIACCNMIARIACC
k-means.33±\pm.00.10±\pm.01.30±\pm.01.48±\pm.00.10±\pm.00.28±\pm.00
Ward.33.08.28.47.09.27
Avg-L (Euc).02.00.06.13.00.06
HypHC.07±\pm.02.02±\pm.01.10±\pm.01.23±\pm.01.01±\pm.00.06±\pm.00
Bisect. k-means.27±\pm.00.10±\pm.00.24±\pm.00.44±\pm.00.09±\pm.00.22±\pm.00
DeepECT.38±\pm.02.21±\pm.02.36±\pm.02.49±\pm.01.14±\pm.01.27±\pm.01
NEST.43±\pm.01.24±\pm.01.42±\pm.01.56±\pm.00.22±\pm.00.35±\pm.01
K=6K = 6K=20K = 20
20 NewsgroupsNMIARIACCNMIARIACC
k-means.44±\pm.00.37±\pm.00.63±\pm.00.53±\pm.00.37±\pm.01.54±\pm.01
Ward.43.37.61.50.32.52
Avg-L (Euc).25.18.40.44.21.27
HypHC.23±\pm.00.17±\pm.00.38±\pm.00.17±\pm.00.06±\pm.00.10±\pm.00
Bisect. k-means.40±\pm.01.33±\pm.01.56±\pm.02.46±\pm.01.30±\pm.00.47±\pm.02
DeepECT.44±\pm.02.42±\pm.05.61±\pm.05.47±\pm.00.31±\pm.01.43±\pm.01
NEST.47±\pm.02.44±\pm.02.68±\pm.01.54±\pm.01.41±\pm.01.57±\pm.02
K=4K = 4K=23K = 23K=133K = 133
Tasic 2018NMIARIACCNMIARIACC
k-means.83±\pm.00.79±\pm.00.77±\pm.00.89±\pm.00.74±\pm.01.77±\pm.01
Ward.82.79.77.89.71.75
Avg-L (Euc).41.18.55.83.56.69
HypHC.85±\pm.00.89±\pm.00.94±\pm.00.41±\pm.00.18±\pm.00.26±\pm.00
Bisect. k-means.82±\pm.00.79±\pm.00.77±\pm.00.87±\pm.00.70±\pm.02.73±\pm.02
DeepECT.65±\pm.02.53±\pm.04.62±\pm.04.87±\pm.01.67±\pm.01.68±\pm.02
NEST.83±\pm.00.79±\pm.00.77±\pm.00.89±\pm.00.74±\pm.01.78±\pm.01

Table 2.

Clustering quality and structure

Figure 2. Clustering quality and structure. (a) CIFAR-100 vehicles 2. Left: t-SNE of the coarse prefix z1:64z_{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 z1:512z_{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.

We next evaluate clustering quality across resolutions (Table 2). Overall, NEST achieves strong performance relative to the baselines at most resolutions across all three real datasets. It performs best at both levels on CIFAR-100 (ACC: .42 and .35) and 20 Newsgroups (ACC: .68 and .57). On Tasic, it matches centroid-based baselines at the coarse level and performs best at both finer resolutions (ACC: .78 at K=23K = 23, .66 at K=133K = 133). On the coarsest Tasic partition, HypHC reaches .94 ACC, while centroid-based methods remain near .77, likely because the coarse Tasic partition is highly imbalanced, a setting in which centroid-based objectives may be disadvantaged.

Next, we measure how well each method balances clustering accuracy with cross-level consistency. Figure 2b shows that NEST achieves the strongest overall trade-off across the three real datasets. It shows both the highest mean accuracy and consistency on CIFAR-100 and Tasic, while on 20 Newsgroups it matches the highest consistency with substantially better accuracy. This indicates that NEST improves clustering quality without sacrificing agreement across resolutions.

Finally, Figure 2c compares computational cost. NEST requires substantially less training compute and memory than DeepECT and HypHC, reflecting the efficiency of learning a residual transformation on top of frozen features rather than training a full deep learning or hyperbolic hierarchical model.

Hierarchy distance in the learned embedding

For a pair of points (i,j)(i,j), let the hierarchy contain LL clustering levels, indexed from coarse (ℓ=1\ell= 1) to fine (ℓ=L\ell= L), and let ℓ∗\ell^* be the first level at which the two points belong to different clusters, i.e., the level just below their lowest common ancestor. We define the hierarchy distance

dT(i,j)=L−ℓ∗+1,d_T(i,j) = L - \ell^* + 1,

the number of levels at which the two points are separated. For example, in a three-level hierarchy, two points that first separate at level 1 have distance 3, whereas points that first separate at level 3 have distance 1; points with the same finest-level label have distance 0. This is a discrete distance derived from the tree, monotone in the depth of the lowest common ancestor, rather than the path length between leaves.

We compare dTd_T with a multiscale distance in the embedding that has the same structure, one term per level,

dz(i,j)=∑ℓ=1Lαℓs^ℓ∥zi(ℓ)−zj(ℓ)∥2,d_z(i,j) = \sum_{\ell=1}^{L} \frac{\alpha_\ell}{\widehat{s}_\ell} \left\lVert z_i^{(\ell)} - z_j^{(\ell)} \right\rVert_2,

where each term uses the level-ℓ\ell prefix with the same scaling as Eq. (2) (Appendix § 13). Because the prefixes are nested, a difference in the coarse coordinates enters every term, just as a pair that separates at the coarsest level is counted at every level by dTd_T. This emphasis on coarse structure is intended, as a coarse split should contribute more to the distance than a split at a finer level. dzd_z is used only for evaluation.

We evaluated the Pearson correlation between dzd_z and dTd_T at initialization and after training. The correlation increases on every dataset, with particularly clear gains on CIFAR-100 (.20 to .43) and balanced tree (.78 to .91), and more modest increases on random branching (.83 to .90), Tasic (.86 to .90), 20 Newsgroups (.42 to .46), and Nested GMM (.87 to .88). Overall, training makes the learned embedding’s multiscale geometry more consistent with the underlying hierarchy.

Ablation

To test the effectiveness of each objective in NEST, we removed each component one at a time from the shared configuration and reported the resulting performance in Table 3. Removing the clustering loss, the separation loss, or the distance scaling consistently reduces ACC and NMI across both CIFAR-100 and Tasic. On CIFAR-100, for example, class-level ACC drops from .35 to .32 without LDEC\mathcal{L}_{\mathrm{DEC}}, to .25 without Lsep\mathcal{L}_{\mathrm{sep}}, and to .30 without the distance scaling (aℓ/s^ℓ=1a_\ell/\widehat{s}_\ell= 1, with the margin ρℓ\rho_\ell kept); similar drops appear at the superclass level and on Tasic.

VariantACCNMI
CIFAR-100, K=20K=20
NEST.42±.01_{\pm.01}.43±.01_{\pm.01}
−Lsep-\mathcal{L}_{\mathrm{sep}}.38±.01_{\pm.01}.39±.00_{\pm.00}
−LDEC-\mathcal{L}_{\mathrm{DEC}}.28±.01_{\pm.01}.30±.01_{\pm.01}
−Lrank-\mathcal{L}_{\mathrm{rank}}.28±.05_{\pm.05}.36±.05_{\pm.05}
−Lwithin-\mathcal{L}_{\mathrm{within}}.41±.01_{\pm.01}.43±.01_{\pm.01}
No distance scaling.36±.01_{\pm.01}.38±.01_{\pm.01}
CIFAR-100, K=100K=100
NEST.35±.01_{\pm.01}.56±.00_{\pm.00}
−Lsep-\mathcal{L}_{\mathrm{sep}}.25±.00_{\pm.00}.48±.00_{\pm.00}
−LDEC-\mathcal{L}_{\mathrm{DEC}}.32±.00_{\pm.00}.52±.00_{\pm.00}
−Lrank-\mathcal{L}_{\mathrm{rank}}.11±.01_{\pm.01}.36±.04_{\pm.04}
−Lwithin-\mathcal{L}_{\mathrm{within}}.35±.01_{\pm.01}.56±.00_{\pm.00}
No distance scaling.30±.01_{\pm.01}.50±.00_{\pm.00}
Tasic, K=133K=133
NEST.66±.01_{\pm.01}.85±.00_{\pm.00}
−Lsep-\mathcal{L}_{\mathrm{sep}}.54±.01_{\pm.01}.80±.00_{\pm.00}
−LDEC-\mathcal{L}_{\mathrm{DEC}}.56±.01_{\pm.01}.84±.00_{\pm.00}
−Lrank-\mathcal{L}_{\mathrm{rank}}.66±.01_{\pm.01}.85±.00_{\pm.00}
−Lwithin-\mathcal{L}_{\mathrm{within}}.57±.01_{\pm.01}.83±.00_{\pm.00}
No distance scaling.56±.02_{\pm.02}.81±.01_{\pm.01}

Table 3. Ablation. Each row removes one component. Metrics mean±s.d. over 3 seeds.

The two anti-collapse regularizers matter when their corresponding failure modes occur. Removing Lrank\mathcal{L}_{\mathrm{rank}} hurts CIFAR-100, reducing ACC from .42 to .28 at K=20K = 20 and from .35 to .11 at K=100K = 100. This degradation coincides with a drop in effective rank from 131–136 to

5–8. Tasic does not exhibit this rank collapse; instead, its main failure mode is excessive contraction at the finest resolution. We applied Lwithin\mathcal{L}_{\mathrm{within}} only at the finest resolution on the real datasets (Table 5).

Conclusion

We introduced NEST, a representation-learning method that encodes several clustering resolutions in nested prefixes of a single embedding and trains them jointly with per-level clustering, center-separation, and anti-collapse objectives. On synthetic hierarchies, NEST demonstrated large clustering gains at middle and finer resolutions. Distances in the learned embedding are also more strongly correlated with the hierarchy distance than distances in the input embedding. On real datasets spanning image, text, and single-cell modalities, NEST shows consistent gains over strong baselines at most clustering resolutions, particularly on CIFAR-100, 20 Newsgroups, and the finer Tasic levels.

Several challenging directions remain. Highly imbalanced hierarchies remain difficult for centroid-based objectives. More broadly, open problems in hierarchical clustering include automatically determining the number of clusters and resolutions, handling irregular or partially observed hierarchies, and scaling nested clustering to larger multimodal representations.

Acknowledgments

All authors declare no competing interests.

This work was supported by the National Science Foundation under Grant CIF-2403452.

AI Use Statement

Generative AI tools were used for language editing, code assistance, and figure refinement. All methods, experiments, analyses, and conclusions were developed and verified by the authors.

Datasets

Synthetic generators. Each of the three synthetic datasets has a three-level hierarchy. Each level is encoded in a separate coordinate block before a fixed random orthonormal transformation is applied, so the hierarchy is not axis-aligned in the observed space. Two parameters control difficulty. The separation factor ϕ\phi sets the distance between sibling cluster centers relative to the within-cluster spread; ϕ≈5\phi\approx5 keeps siblings well separated, while ϕ≈2.5\phi\approx2.5 makes them overlap. The scale-separation factor κ∈(0,1)\kappa\in(0, 1) controls the relative magnitude of successive hierarchical levels, disp⁡ℓ=disp⁡Lκ−(L−ℓ)\operatorname{disp}_{\ell} = \operatorname{disp}_{L}\kappa^{-(L-\ell)}; smaller κ\kappa produces well-separated scales, whereas κ→1\kappa\to1 makes distinctions across levels comparable in magnitude. The generators below are common to every synthetic run; the real-data model settings are in Table 5.

Nested GMM: K=(4,16,64)K = (4, 16, 64), obs_dim = 99, data blocks (33, 33, 33), branching 4, base_scale = 8.0, κ=0.4\kappa= 0.4, rtarget=0.55r_{\mathrm{target}} = 0.55, 200 points/leaf. Balanced tree: K=(3,7,15)K = (3, 7, 15), obs_dim = 20, blocks (7, 7, 6), ϕ=4\phi= 4, κ=0.6\kappa= 0.6, 80 points/node. Random-branching tree: K=(4,13,52)K = (4, 13, 52), 1 + Poisson(3) children per node (at most 6), depth 4, ϕ=4\phi= 4, κ=0.6\kappa= 0.6, 50 points/node, topology fixed across seeds. In all three the clean data is mapped through a fixed random orthonormal rotation and augmented with 50 nuisance coordinates of standard deviation σn=1\sigma_{\mathrm{n}} = 1, giving 149 observed dimensions for the GMM and 70 for the two trees. Geometry and sampling noise are redrawn per seed at fixed cluster counts.

CIFAR-100. We use the frozen 512-dimensional SimCLR ResNet-18 pretext features released with SCAN [6]: the CIFAR-100 pretext checkpoint simclr_cifar100.pth.tar from the authors’ repository (wwangansbeke/Unsupervised-Classification), read at the backbone output before the 128-dimensional projection head, with SCAN’s image normalization. Features of all 60,000 train and test images are standardized per dimension with statistics computed over those 60,000; no labels or self-labeling are used. The 20 superclasses and 100 classes define K=(20,100)K = (20, 100). Every method, NEST included, is fit on the same fixed subset of 5,000 images drawn as 50 per class (seed 0), and scored on all of them (evaluation points, below).

Tasic et al. [19]. We use the released preprocessed scRNA-seq representation from Tasic et al. [19] (library-size normalization, log⁡2\log_2 transformation, highly-variable-gene selection, and PCA to 50 dimensions) for 23,822 cells, the matrix tasic-pca50.npy distributed with the berenslab single-cell visualization code, used raw (not standardized). Labels come from the Allen Institute 2018-06-14 release of the mouse VISp and ALM data (mouse_VISp_2018-06-14_samples-columns.csv, mouse_ALM_2018-06-14_samples-columns.csv). The official Allen class, subclass, and cluster annotations define K=(4,23,133)K = (4, 23, 133). Samples are aligned to the released PCA representation using sample_name; the join is one-to-one with no missing cells. The resulting taxonomy is strictly nested: each cluster belongs to one subclass and each subclass to one class. The official four-way class annotation is used throughout. For sensitivity analysis only, we also consider the broader three-way grouping obtained by merging Endothelial with Non-Neuronal cells.

20 Newsgroups. 20 Newsgroups [12] is a text classification dataset containing approximately 20,000 documents organized into 20 topic categories. The 18,846 posts of the scikit-learn 20newsgroups “all” set, with headers, footers and quotes removed, are embedded with the frozen sentence encoder sentence-transformers/all-MiniLM-L6-v2 [17, 22] (maximum sequence length 256, 384 dimensions) and standardized per dimension. The 20 newsgroups define the fine level; grouping them by name gives the 6 coarse topics comp (5 groups), rec (4), sci (4), politics (3), religion (3: alt.atheism, soc.religion.christian, talk.religion.misc) and forsale (1), K=(6,20)K = (6, 20). Coarse classes hold 975 to 4,891 posts.

Evaluation. On the datasets, every method is fit on all points without labels and scored on all points (5,000 images for CIFAR-100, 23,822 cells for Tasic, 18,846 posts for 20 Newsgroups). Labels are not used for training, initialization, or stopping; they are used only to construct the class-balanced CIFAR-100 subset and for evaluation.

Geometric motivation for the 4r separation margin

In Section 3, we set the separation margin to ρℓ=4r^ℓ\rho_\ell= 4\hat{r}_\ell. The factor of 4 is motivated by the following geometric argument.

Let rℓr_\ell denote an upper bound on the distance from any point in a cluster to its center at level ℓ\ell, and let sℓs_\ell denote the distance between two cluster centers. Since each point can lie up to rℓr_\ell from its cluster center, two points within the same cluster can be as far as 2rℓ2r_\ell apart.

For two different clusters, the closest pair of points occurs when both points lie toward the other cluster, giving a minimum cross-cluster distance of

sℓ−2rℓ.s_\ell- 2r_\ell.

Requiring this distance to be at least the maximum within-cluster distance gives

sℓ−2rℓ≥2rℓ,s_\ell- 2r_\ell\ge2r_\ell,

making

sℓ≥4rℓ.s_\ell\ge4r_\ell.

In real data, the maximum point-to-center distance is often determined by a small number of outlying points. We therefore use the mean point-to-center distance at initialization, r^ℓ\hat{r}_\ell, as a robust estimate of the cluster scale. Motivated by the geometric bound above, we set

ρℓ=4r^ℓ.\rho_\ell= 4\hat{r}_\ell.

Because r^ℓ\hat{r}_\ell is a mean rather than an upper bound, the inequality above is no longer guaranteed for every point; the factor 4 is a heuristic taken from the worst case.

Baseline settings

kk-means uses n_init=20. Ward and average linkage construct a single dendrogram that is cut at each target KK. Average linkage uses Euclidean distance: every method in Table 2, NEST included, then operates on the same Euclidean geometry of the frozen input, so differences reflect the clustering procedure rather than a change of metric on the input. HDBSCAN uses min_cluster_size = \max(5, N/2k), min_samples = 5, EOM selection, with noise points counted as one label. HypHC uses rank-2 embeddings, 50 epochs of Riemannian Adam, and greedy tree decoding, with 504,000 triplets for CIFAR-100 and 20 Newsgroups and 2,000,000 for Tasic. DeepECT uses its published configuration: an autoencoder (DD–500–500–2000–10) pretrained for 50,000 steps, after which the cluster tree is grown by splitting the leaf with the largest within-cluster error every 500 steps until it has as many leaves as the finest level, followed by 20,000 further steps; the flat partition at each KK is the tree as it stood when it had KK leaves. On every dataset each NEST level is read out by its own centers on the prefix z1:mℓz_{1:m_\ell}, while the baselines run on the input. Stochastic methods are reported over seeds {0,1,2}\{0,1,2\} on real data and over 5 seeds on synthetic data.

Metric definitions

ACC aligns clusters to classes by the Hungarian algorithm [10]. With KK predicted clusters and KK true classes at a level, we form the K×KK \times K matrix of class–cluster co-occurrence counts and take the one-to-one assignment that maximizes the total count on the diagonal; ACC is that total divided by nn. Wherever a cluster is called the one matched to a class, this is the assignment meant. Because it is one-to-one, a class whose points fall mostly into a cluster already claimed by another class is matched to whatever cluster remains, possibly an empty one; ARI and NMI do not use this matching.

Cross-level consistency. ACC, ARI and NMI score each level separately, so a method can score well at every level while its levels disagree about the hierarchy, for example by placing a point in a coarse cluster matched to vehicles 1 but in a fine cluster matched to apple. Cross-level consistency measures this agreement. For each pair of adjacent levels, we match each level’s clusters to its true classes with the Hungarian assignment used for ACC. Each point ii then has a predicted coarse class c^i\hat{c}_i, the class matched to its coarse cluster, and a predicted fine class f^i\hat{f}_i, the class matched to its fine cluster. Point ii is consistent when the true parent of f^i\hat{f}_i is c^i\hat{c}_i, that is, par⁡(f^i)=c^i\operatorname{par}(\hat{f}_i)=\hat{c}_i. The consistency of a level pair is the fraction of consistent points, and a dataset’s consistency is the mean over its adjacent level pairs. Consistency does not require correctness: a point is consistent even if both of its predicted classes are wrong, as long as they agree with the true hierarchy. A method that cuts one dendrogram at both levels produces nested clusters by construction, but it need not be fully consistent, because each level is matched to its classes separately.

Hierarchy-distance correlation

We measure how well pairwise distances in the learned embedding reflect the ground-truth hierarchy. Equation (2) defines the scaled distance between a data point and a cluster center at level ℓ\ell. Here, we use the same scaling to measure the distance between two data points. For a pair (i,j)(i,j), we define

dz(i,j)=∑ℓ=1Lαℓs^ℓ∥zi(ℓ)−zj(ℓ)∥2d_z(i,j)=\sum_{\ell=1}^{L}\frac{\alpha_\ell}{\hat{s}_\ell}\left\lVert z_i^{(\ell)}-z_j^{(\ell)}\right\rVert_2

where zi(ℓ)z_i^{(\ell)} and zj(ℓ)z_j^{(\ell)} are the level-ℓ\ell prefixes of the two points.

Let ℓ∗\ell^* denote the coarsest level at which the ground-truth cluster labels of ii and jj differ. We define

dT(i,j)=L−ℓ∗+1,d_T(i,j)=L-\ell^*+1,

the number of levels at which the two points are separated, so pairs that separate earlier in the hierarchy have larger hierarchy distance. Because the prefixes are nested, a difference in the coarse coordinates enters every term of dzd_z, in the same way that a coarse split is counted at every level by dTd_T; dzd_z is used only for evaluation.

We sample 2,000 pairs for each distinct value of dTd_T and compute the Pearson correlation between dzd_z and dTd_T over the resulting pairs.

Training compute and memory

Figure 2c reports training compute in floating-point operations (FLOPs) and memory. FLOPs count the multiplications and additions of a method’s full training run: one forward pass through each layer, tripled to include the backward pass, summed over every training sample and step. Initialization, optimizer updates and evaluation are not counted. Memory is the space needed to hold the training data and the learned parameters in 32-bit floats.

HypHC’s FLOPs and memory are computed differently from those of NEST and DeepECT, which are counted over the individual training points they process. HypHC instead trains on triplets of points: it learns a hierarchy by minimizing a continuous version of Dasgupta’s cost, which is a sum over triplets, where for each triplet the two most similar points should be merged lowest in the tree. Using every triplet is infeasible, since their number grows with the cube of the number of points (about 2×10102\times10^{10} for the 5,000 CIFAR-100 images), so HypHC is trained on a fixed random sample of triplets: 504,000 for CIFAR-100 and 20 Newsgroups and 2,000,000 for Tasic, for 50 epochs each. Its FLOPs are counted over these triplets and also include building the full matrix of pairwise similarities and decoding the tree, both of which grow with the square of the number of points. Its memory is dominated by that similarity matrix, rather than by the training data and parameters as for NEST and DeepECT.

Single-level controls

To separate the effect of training the levels jointly from the effect of the NEST objective itself, we trained each level on its own in two ways: NEST with a single head on the full embedding, every other setting of the shared configuration unchanged, and single-scale DEC (autoencoder D→512→256→64D\to512\to256\to64, 100 warm-up epochs, 160 DEC epochs) at each KℓK_\ell. Both were fit and scored on all points over seeds 0, 1 and 2 and compared with the jointly trained Table 2 model. We found that joint training raises the coarsest level on every dataset and is above or within one standard deviation of single-level NEST elsewhere, and that single-scale DEC is below NEST except at the two coarser Tasic levels, where it is within one standard deviation (Table 4).

Table 4: Joint versus single-level training. ACC / ARI / NMI per level, mean±\pms.d. over 3 seeds, all points scored. Bold is the best of the three after rounding, ties share it.

DatasetKKNEST, joint ACCNEST, joint ARINEST, joint NMINEST, one level ACCNEST, one level ARINEST, one level NMIDEC, one level ACCDEC, one level ARIDEC, one level NMI
CIFAR-10020.42±\pm.01.24±\pm.01.43±\pm.02.38±\pm.02.20±\pm.02.38±\pm.01.34±\pm.01.17±\pm.00.39±\pm.00
CIFAR-100100.35±\pm.01.22±\pm.00.56±\pm.00.36±\pm.01.22±\pm.01.55±\pm.01.27±\pm.01.11±\pm.01.51±\pm.00
20 Newsgroups6.68±\pm.01.44±\pm.02.47±\pm.02.51±\pm.00.30±\pm.00.40±\pm.00.57±\pm.05.38±\pm.01.40±\pm.01
20 Newsgroups20.57±\pm.02.41±\pm.01.54±\pm.01.56±\pm.02.40±\pm.02.54±\pm.01.52±\pm.01.35±\pm.00.51±\pm.01
Tasic 20184.77±\pm.00.79±\pm.00.83±\pm.00.72±\pm.01.62±\pm.01.61±\pm.01.76±\pm.02.76±\pm.06.79±\pm.06
Tasic 201823.78±\pm.01.74±\pm.01.89±\pm.00.78±\pm.01.74±\pm.00.89±\pm.00.78±\pm.02.75±\pm.02.89±\pm.00
Tasic 2018133.66±\pm.01.64±\pm.01.85±\pm.00.63±\pm.01.61±\pm.01.85±\pm.00.56±\pm.01.50±\pm.00.84±\pm.00

Table 4.

Hyperparameters

Table 5 shows the hyperparameters we used for each dataset.

Sensitivity analysis

As in other unsupervised clustering settings, hyperparameter selection is challenging because ground-truth labels are unavailable for validation. We therefore limit dataset-specific tuning and share most settings across datasets (Table 5). The few dataset-specific settings are selected from a small number of variants evaluated on the reported data. Figure 3 varies each of these settings individually around the reported value and shows similar performance across a range of nearby values.

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: λrank\lambda_{\mathrm{rank}} with λwithin\lambda_{\mathrm{within}} fixed; λwithin\lambda_{\mathrm{within}} with λrank\lambda_{\mathrm{rank}} fixed; coarse prefix width m1m_1; level weights (real data: coarse weight a1a_1, others 1; synthetic: aℓ=rℓ−1a_\ell= r^{\ell-1} with the regularization weights fixed). Dashed line: reported configuration.

Figure 3 changes one setting at a time around the reported configuration: the anti-collapse regularization weights λrank\lambda_{\mathrm{rank}} and λwithin\lambda_{\mathrm{within}} (each varied with the other fixed), the coarse prefix width m1m_1, and the relative level weights aℓa_\ell. Each point reports the difference in ACC between NEST and the strongest baseline at the corresponding level, evaluated on all points.

On CIFAR-100, NEST remains above the strongest baseline at both resolutions for λrank≥1\lambda_{\mathrm{rank}} \ge1, for every tested λwithin\lambda_{\mathrm{within}}, for coarse-prefix widths between D/16D/16 and D/4D/4, and for a1≤1a_1 \le1. Removing Lrank\mathcal{L}_{\mathrm{rank}} primarily degrades the fine, class-level clustering. Tasic is comparatively insensitive to λrank\lambda_{\mathrm{rank}} and m1m_1; removing Lwithin\mathcal{L}_{\mathrm{within}} mainly hurts the finest level. On 20 Newsgroups, performance remains similar across a range of nearby settings, with the finest level remaining above baseline for λrank<0.3\lambda_{\mathrm{rank}} < 0.3 and for every tested λwithin\lambda_{\mathrm{within}}, while the coarse-level margin varies with prefix width and becomes smaller near D/8D/8.

The synthetic datasets show a similar pattern. On the balanced and random-branching trees, the middle and finest levels remain above the baselines throughout the tested ranges. The balanced-tree coarse level also remains above baseline across most tested prefix widths. Nested GMM shows greater variation at the finest level, where improvements appear once λrank\lambda_{\mathrm{rank}} or λwithin\lambda_{\mathrm{within}} reaches the reported value and with the 1:2:4 level weighting.

References

  1. [1]Yash Bhalgat, Iro Laina, João F. Henriques, Andrew Zisserman, and Andrea Vedaldi. N2f2: Hierarchical scene understanding with nested neural feature fields, 2024. URL https://arxiv.org/abs/2403.10997.
  2. [2]Ricardo J. G. B. Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Jian Pei, Vincent S. Tseng, Longbing Cao, Hiroshi Motoda, and Guandong Xu, editors, PAKDD (2), volume 7819 of Lecture Notes in Computer Science, pages 160–172. Springer, 2013. ISBN 978-3-642-37456-2. URL http://dblp.uni-trier.de/db/conf/pakdd/pakdd2013-2.html#CampelloMS13.
  3. [3]Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features, 2019. URL https://arxiv.org/abs/1807.05520.
  4. [4]Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering, 2020. URL https://arxiv.org/abs/2010.00402.
  5. [5]Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering, 2015. URL https://arxiv.org/abs/1510.05043.
  6. [6]Wouter Van Gansbeke, Simon Vandenhende, Stamatis Georgoulis, Marc Proesmans, and Luc Van Gool. Learning to classify images without labels. CoRR, abs/2005.12320, 2020. doi: 10.48550/ARXIV.2005.12320. URL https://doi.org/10.48550/arXiv.2005.12320.
  7. [7]Hans W. A. Hanley and Zakir Dumeric. Hierarchical level-wise news article clustering via multilingual matryoshka embeddings, 2025. URL https://arxiv.org/abs/2506.00277.
  8. [8]J. A. Hartigan and M. A. Wong. A k-means clustering algorithm. JSTOR: Applied Statistics, 28(1):100–108, 1979.
  9. [9]Jiabo Huang, Shao-Gang Gong, and Xiatian Zhu. Deep semantic clustering by partition confidence maximisation. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8846–8855, 2020. URL https://api.semanticscholar.org/CorpusID:219966514.DOI
  10. [10]H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83–97, 1955. doi: https://doi.org/10.1002/nav.3800020109. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109.
  11. [11]Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain, and Ali Farhadi. Matryoshka representation learning, 2024. URL https://arxiv.org/abs/2205.13147.
  12. [12]Ken Lang. Newsweeder: learning to filter netnews. In Proceedings of the Twelfth International Conference on Machine Learning, ICML’95, page 331–339, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603778.DOI
  13. [13]Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive clustering, 2020. URL https://arxiv.org/abs/2009.09687.
  14. [14]Dominik Mautz, Claudia Plant, and Christian Böhm. Deep embedded cluster tree. In 2019 IEEE International Conference on Data Mining (ICDM), pages 1258–1263, 2019. doi: 10.1109/ICDM.2019.00157.DOI
  15. [15]Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS, pages 849–856. MIT Press, 2001. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100.
  16. [16]Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. CoRR, abs/1705.08039, 2017. doi: 10.48550/ARXIV.1705.08039. URL https://doi.org/10.48550/arXiv.1705.08039.
  17. [17]Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks, 2019. URL https://arxiv.org/abs/1908.10084.
  18. [18]Michael S. Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques, 2000. URL https://hdl.handle.net/11299/215421.
  19. [19]Bosiljka Tasic, Zizhen Yao, Lucas T. Graybuck, Kimberly A. Smith, Thuc Nghi Nguyen, Darren Bertagnolli, Jeff Goldy, Emma Garren, Michael N. Economo, Sharad Viswanathan, Osnat Penn, Trygve Bakken, Wilas Menon, Jeremy Miller, Olivia Fong, Karla E. H. Hirokawa, Kanan Lathia, Christine Rimorin, Melissa Tieu, Rebecca Larsen, Tamara Casper, Eliza Barkan, Matthew Kroll, Sheana Parry, Nadiya V. Shapovalova, Daniel Hirschtstein, Julie Pendergraft, Heather A. Sullivan, Tae Kyung Kim, Aaron Szafer, Nick Dee, Peter Groblewski, Ian Wickersham, Ali Cetin, Julie A. Harris, Boaz P. Levi, Susan M. Sunkin, Linda Madisen, Tanya L. Daigle, Loren Looger, Amy Bernard, John Phillips, Ed Lein, Michael Hawrylycz, Karel Svoboda, Allan R. Jones, Christof Koch, and Hongkui Zeng. Shared and distinct transcriptomic cell types across neocorti- cal areas. Nature, 563(7729):72–78, 2018. doi: 10.1038/s41586-018-0654-5.
  20. [20]Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(86):2579–2605, 2008. URL http://jmlr.org/papers/v9/vandermaaten08a.html.
  21. [21]Shashanka Venkataramanan, Valentinos Pariza, Mohammedreza Salehi, Lukas Knobel, Spyros Gidaris, Elias Ramzi, Andrei Bursuc, and Yuki M. Asano. Franca: Nested matryoshka clustering for scalable visual representation learning, 2026. URL https://arxiv.org/abs/2507.14137.
  22. [22]Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. MiniLM: Deep self-attention distillation for task-agnostic compression of pre-trained transformers, 2020. URL https://arxiv.org/abs/2002.10957.
  23. [23]Joe H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58:236–244, 1963. URL https://api.semanticscholar.org/CorpusID:32863022.
  24. [24]Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering, 2019. URL https://arxiv.org/abs/1904.06925.
  25. [25]Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis, 2016. URL https://arxiv.org/abs/1511.06335.
  26. [26]Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters, 2016. URL https://arxiv.org/abs/1604.03628.
  27. [27]Michał Znaleźniak, Przemysław Rola, Patryk Kaszuba, Jacek Tabor, and Marek Śmieja. Contrastive hierarchical clustering, 2023. URL https://arxiv.org/abs/2303.03389.

Paper details

vlnc:W_chn4acam
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Generative AI tools

View statement
Looking for related papers…
Contents